Note ABES Apprentissage automatique séquentiel pour les systèmes éducatifs intelligents Sequential machine learning for intelligent tutoring systems Environnement informatique pour l’apprentissage humain Modèle du bandit à plusieurs bras Bandits décroissants Processus de décision markovien partiellement observable Machine Learning Reinforcement Learning Bandits Intelligent tutoring systems (ITS) Adaptive Learning Environnement d'apprentissage personnel Plateformes d'apprentissage en ligne Éducation et informatique Apprentissage par renforcement (intelligence artificielle) Prise de décision (statistique) Proposer des séquences adaptatives d’exercices dans un Environnement informatique pourl’Apprentissage Humain (EIAH) nécessite de caractériser les lacunes de l’élève et d’utilisercette caractérisation dans une stratégie pédagogique adaptée. Puisque les élèves ne fontque quelques dizaines de questions dans une session de révision, ces deux objectifs sonten compétition. L’apprentissage automatique appelle problème de bandits ces dilemmesd’exploration-exploitation dans les prises de décisions séquentielles. Dans cette thèse,nous étudions trois problèmes de bandits pour une application dans les systèmes éducatifsadaptatifs.Les bandits décroissants au repos sont un problème de décision séquentiel dans lequel larécompense associée à une action décroît lorsque celle-ci est sélectionnée. Cela modélisele cas où un élève progresse quand il travaille et l’EIAH cherche à sélectionner le sujetle moins maîtrisé pour combler les plus fortes lacunes. Nous présentons de nouveauxalgorithmes et nous montrons que pour un horizon inconnu T et sans aucune connaissancesur la décroissance des K bras, ces algorithmes atteignent une borne de regret dépendantedu problème O(logT); et une borne indépendante du problème Oe(pKT). Nos résultatsaméliorent substantiellement l’état de l’art, ou seule une borne minimax Oe(K1=3T2=3) avaitété atteinte. Ces nouvelles bornes sont à des facteurs polylog des bornes optimales sur leproblème stationnaire, donc nous concluons : les bandits décroissants ne sont pas plus dursque les bandits stationnaires.Dans les bandits décroissants sans repos, la récompense peut décroître à chaque tour pourtoutes les actions. Cela modélise des situations différentes telles que le vieillissementdu contenu dans un système de recommandation. On montre que les algorithmes conçuspour le problème "au repos" atteignent les bornes inférieures agnostiques au problèmeet une borne dépendante du problème O(logT). Cette dernière est inatteignable dans lecas général où la récompense peut croître. Nous concluons : l’hypothèse de décroissancesimplifie l’apprentissage des bandits sans repos.Viser le sujet le moins connu peut être intéressant avant un examen, mais pendant lecursus - quand tous les sujets ne sont pas bien compris - cela peut mener à l’échec del’apprentissage de l’étudiant. On étudie un Processus de Décision Markovien PartiellementObservable (POMDP, selon l’acronyme anglais) dans lequel on cherche à maîtriser le plusde sujets le plus rapidement possible. On montre que sous des hypothèses raisonnablessur l’apprentissage de l’élève, la meilleure stratégie oracle sélectionne le sujet le plusconnu sous le seuil de maîtrise. Puisque cet oracle optimal n’a pas besoin de connaîtrela dynamique de transition du POMDP, nous proposons une stratégie apprenante avecdes outils "bandits" classiques, en évitant ainsi les méthodes gourmandes en données del’apprentissage de POMDP. Designing an adaptive sequence of exercises in Intelligent Tutoring Systems (ITS) requiresto characterize the gaps of the student and to use this characterization in a relevantpedagogical strategy. Since a student does no more than a few tens of exercises in a session,these two objectives compete. Machine learning called these exploration-exploitationtrade-offs in sequential decision making the bandits problems. In this thesis, we studydifferent bandits setups for intelligent tutoring systems.The rested rotting bandits are a sequential decision problem in which the reward associatedwith an action may decrease when it is selected. It models the situation where the studentimproves when he works and the ITS aims the least known subject to fill the most importantgaps. We design new algorithms and we prove that for an unknown horizon T, and withoutany knowledge on the decreasing behavior of the K arms, these algorithms achieve problemdependentregret bound of O(logT); and a problem-independent one of Oe(pKT). Ourresult substantially improves over existing algorithms, which suffers minimax regretOe(K1=3T2=3). These bounds are at a polylog factor of the optimal bounds on the classicalstationary bandit; hence our conclusion: rotting bandits are not harder than stationary ones.In the restless rotting bandits, the reward may decrease at each round for all the actions.They model different situations such as the obsolescence of content in recommendersystems. We show that the rotting algorithms designed for the rested case match theproblem-independent lower bounds and a O(logT) problem-dependent one. The latter wasshown to be unachievable in the general case where rewards can increase. We conclude:the rotting assumption makes the restless bandits easier.Targeting the least known topic may be interesting before an exam but during the curriculum- when all the subjects are not yet understood - it can lead to failure in the learning of thestudent. We study a Partially Observable Markov Decision Process in which we aim atmastering as many topics as fast as possible. We show that under relevant assumptions onthe learning of the student, the best oracle policy targets the most known topic under themastery threshold. Since this optimal oracle does not need to know the transition dynamicsof the POMDP, we design a learning policy with classical bandits tools, hence avoidingthe data-intensive methods of POMDP learning. Electronic Thesis or Dissertation Text en PDF 18248144 https://pepite-depot.univ-lille.fr/LIBRE/EDSPI/2020/2020LILUI084.pdf https://theses.hal.science/tel-03490620 https://theses.hal.science/tel-03490620 https://theses.hal.science/tel-03490620 https://theses.hal.science/tel-03490620 https://theses.fr/2020LILUI084/abes https://theses.hal.science/tel-03490620 https://theses.hal.science/tel-03490620 https://theses.hal.science/tel-03490620 Seznec Julien Seznec 1993-01-08 FR 258921420 https://theses.fr/2020LILUI084 2020LILUI084 https://doi.org/10.70675/7b92f6e7z5ec9z4ffaz917bz40903858426b 2020-12-15 Informatique et applications Université de Lille (2018-2021) 223446556 Doctorat Docteur es non oui Valko Michal MADS_DIRECTEUR_DE_THESE_1 22360934X Lazaric Alessandro MADS_DIRECTEUR_DE_THESE_2 188701486 Mougeot Mathilde MADS_PRESIDENT_DU_JURY 191563811 Banon Jonathan MADS_MEMBRE_DU_JURY_1 Grünewälder Steffen MADS_MEMBRE_DU_JURY_2 Lopes Manuel MADS_MEMBRE_DU_JURY_3 188282947 Stoltz Gilles MADS_RAPPORTEUR_1 091575419 Garivier Aurélien MADS_RAPPORTEUR_2 111902495 École doctorale Sciences pour l'ingénieur (Lille ; 1992-2021) MADS_ECOLE_DOCTORALE_1 147297028 Centre Inria de l'Université de Lille MADS_PARTENAIRE_DE_RECHERCHE_1 185432247 Centre de Recherche en Informatique, Signal et Automatique de Lille MADS_PARTENAIRE_DE_RECHERCHE_2 18388695X Inria Lille - Nord Europe MADS_PARTENAIRE_DE_RECHERCHE_3 104752 inria scool MADS_PARTENAIRE_DE_RECHERCHE_4 1042631 ddc:004 Valko Michal Lazaric Alessandro Mougeot Mathilde Banon Jonathan Grünewälder Steffen Lopes Manuel Stoltz Gilles Garivier Aurélien École doctorale Sciences pour l'ingénieur (Lille) Institut national de recherche en informatique et en automatique (Inria Lille - Nord Europe) Centre de recherche en informatique, signal et automatique de Lille (CRIStAL) Inria Lille - Nord Europe inria scool PDF 18248144