Apprentissage automatique séquentiel pour les systèmes éducatifs intelligents
Julien Seznec · theses.fr (ABES) · 2020
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.