Soutenance mémoire
Définition de l’ARI
Nous voilà donc armés pour résoudre (de manière approchée) le problème du contrôle optimal, pour peu que l’on dispose d’une description de la tâche à accomplir sous la forme d’une fonction de récompense R et d’échantillons représentatifs du problème.
Définition du problème La question qui se pose maintenant est de savoir dans quelle mesure il est possible d’automatiquement déduire d’une trace du comportement de l’expert une description de son but sous la forme d’une fonction de récompense. Cette méthode d’imitation a été suggérée pour la première fois par Russell [Rus98]. L’état de l’art sera traité au chapitre suivant, nous nous attelons ici à trouver une formulation mathématique du problème et à exposer les notions nécessaires à l’analyse des méthodes existantes et à l’introduction des nouvelles approches que nous proposons. Outre l’intérêt intrinsèque de la découverte des motivations de l’expert, apprendre une fonction de récompense correspondant au comportement de l’expert permet de soigner les méthodes d’imitation de leur “myopie” (sous-section 2.1.6), en guidant l’agent vers une imitation non pas de la manière dont l’expert accomplit la tâche, comme le fait l’imitation directe de la politique, mais du but de l’expert. Dans le formalisme des PDM introduit plus tôt, l’expression du problème de l’ARI est de prime abord simple : on suppose que la politique de l’expert pE est une politique optimale pour une certaine fonction de récompense RE qu’il s’agit de trouver. Les choses se corsent malheureusement extrêmement rapidement. Tout d’abord, cette formulation n’est pas un problème mathématique bien posé au sens d’Hadamard [Had02] : il existe en effet de multiples solutions, dont au moins une est dégénérée, la récompense uniformément nulle. Tous les comportements (donc celui de l’expert) ont la même valeur (0) pour cette récompense, donc tous sont optimaux. En inversant, la politique de l’expert est optimale pour la récompense nulle, qui est donc solution du problème. Plus subtilement, utiliser le formalisme des PDM présuppose que certaines conditions sont réunies, notamment en ce qui concerne les espaces d’état et d’action. Il faut être en mesure de définir un espace d’état markovien, afin qu’un agent puisse prendre sa décision quant à l’action en se basant uniquement sur les informations de l’état. Il faut également être en mesure d’obtenir une trace de l’expert (le problème se pose déjà pour l’imitation directe de la politique). L’espace d’action doit rester discret et de faible cardinal si l’on veut que l’immense majorité des approches d’ARI y restent tractables.
Méthodes nécessitant la résolution répétée d’un PDM
Cette nécessité est lourde de conséquences quant à l’usage pratique d’un algorithme d’ARI. La résolution du problème de l’AR nécessite en effet soit beaucoup de données pour sa résolution off-policy, soit l’accès à un simulateur ou au système réel pour sa résolution on-policy. Abbeel et Ng [AN04] proposent l’algorithme Projection Inverse Reinforcement Learning (PIRL) dans un travail séminal dont la structure va être reprise (plus ou moins consciemment) par plusieurs autres approches. La récompense est paramétrée linéairement, de fait la notion d’attribut moyen apparaît assez logiquement (Équation 2.54). Elle obtient même une place centrale dans cette approche itérative de l’ARI. L’idée (résumée algorithme 4) est, à chaque itération, d’apprendre la politique optimale pour la fonction de récompense courante (via un algorithme d’AR). L’attribut moyen de cette politique est alors évalué. La fonction de coût que minimise l’approche joue sur une définition de la proximité d entre l’attribut moyen de cette politique et l’attribut moyen de la politique de l’expert. A chaque itération cette proximité est évaluée, et le vecteur de paramètre q de la récompense change dans une direction (donnée par une règle de mise à jour u) qui va chercher à réduire cette distance. La justification est que deux politiques d’attributs moyens semblables auront des fonctions de valeur semblables pour toute récompense, y compris donc la récompense inconnue optimisée par l’expert (Proposition 1). Le seul bémol de cette logique est que la réciproque peut être fausse, deux attributs extrêmement différents peuvent mener à la même valeur. Plusieurs autres approches sont basées sur le même schéma itératif. Une revue en est proposée par Neu et Szepesvári [NS09]. PIRL est intrinsèquement un algorithme d’imitation plus que d’ARI, en ce sens que la sortie est une politique stochastique (plus précisément un mélange de politiques déterministes) et non une fonction de récompense. Il est cependant facile de le “convertir” en extrayant la meilleure fonction de récompense, celle liée à la plus petite distance entre attribut moyen de la politique optimale et attribut moyen de l’expert. La technique proposée dans [NS07] (Policy Matching (PM)) repose sur une réduction des désaccords entre la politique de l’expert et la politique à l’itération courante, via une recherche dans l’espace des paramètres q de la récompense. Le lien unissant récompense et politique, qui est lié à la résolution d’un PDM, est ici caractérisé par des outils d’analyse fonctionnelle afin d’extraire une solution analytique du problème qui soit également calculable. Cette contribution présente une plus grand robustesse aux changements d’échelle des attributs. On a vu en section 3.1 que l’ensemble des politiques optimales est stable par dilatation de la récompense, et donc également par dilatation des attributs. Cette plus grande robustesse est donc signe d’une formulation plus saine de l’ARI. Le bruit dans les attributs est également mieux géré.
Méthodes ne nécessitant pas la résolution répétée d’un PDM
Les problèmes intrinsèquement liés à la structure itérative des premiers algorithmes d’ARI étant identifiés, un regain de créativité a permis l’émergence d’approches hétérogènes ces dernières années. Un schéma itératif (mais sans lien évident avec le schéma itératif classique de la section précédente) permet à Levine, Popovic et Koltun [LPK10] d’effectuer de la sélection d’attributs tout en apprenant la récompense, à l’aide d’une méthode semblable dans sa motivation au boosting opéré dans [Rat+07]. La méthode de Levine, Popovic et Koltun [LPK10] semble cependant plus générique, et l’idée qu’une récompense “simple” est préférable y est enracinée. La tractabilité n’est malheureusement pas rendezvous. Présenté comme une approche supervisée de l’imitation, la méthode de Melo et Lopes [ML10] repose sur une notion particulière de distance dans un PDM. Cette distance n’est pas uniquement basée sur la définition de l’espace d’état (comme l’est par exemple la distance euclidienne standard) mais prend en compte la dynamique du PDM afin que deux états semblables pour le problème qui nous préoccupe (permettant d’accéder aux mêmes états en effectuant la même action) aient une distance nulle. Le calcul de cette distance cache la résolution du PDM par des méthodes de PD, on trouve le point fixe d’un opérateur par son application répétée. Bien que la récompense n’apparaisse pas explicitement dans l’exposition de la méthode, le raisonnement qui définit l’échantillonnage interactif et la politique renvoyée par l’algorithme est similaire a ce qui a été proposé par Lopes, Melo et Montesano [LMM09]. Raisonnant selon la même logique bayésienne que Ramachandran et Amir, mais présentant la particularité de ne pas faire appel à une approximation linéaire de la fonction de récompense, le travail de Levine, Popovic et Koltun [LPK11] utilise des PG dans une approche itérative (appelée Gaussian Processes Inverse Reinforcement Learning (GPIRL)) qui apprend en même temps la fonction de récompense et le noyau permettant d’en représenter la structure. Elle souffre d’un problème de tractabilité que les auteurs résolvent en partie en proposant une version échantillonnée sur une partie de l’espace d’état, ce qui induit d’autres problèmes, notamment au niveau de la qualité de la généralisation. Cette approche pourrait facilement être augmentée d’un schéma d’échantillonnage actif en raison de la présence de l’information d’incertitude dans les PG. Les PG sont aussi présents chez Qiao et Beling [QB11], dans une approche également bayésienne mais beaucoup plus analytique. Il ne s’agit pas simplement de calculer un maximum a posteriori sur une classe de fonctions de récompenses : le modèle graphique bayésien est sémantiquement plus riche (et donc malheureusement plus lourd), chaque choix de l’expert rajoute une relation dans un modèle bayésien sur les Q valeurs. Cette approche semble ne pas souffrir des problèmes de généralisation qui pénalisent GPIRL, mais paraît encore moins tractable et est réservée aux PDM discrets.
SCIRL appliqué au mountain-car
Comme nous l’avons précisé section B.2, la démonstration de l’expert ignore toute une partie de l’espace d’état, le quadrant Sud-Est où la voiture est proche du but, mais s’en éloigne. Les données de l’expert sont collectées, en choisissant un état de départ telle que la position est dans l’intervalle [1.2; 0.9] et la vitesse dans [0.07; 0]. La trajectoire est poursuivie jusqu’à ce que l’expert atteigne le but. Autant de trajectoires que nécessaire sont effectuées pour obtenir des ensembles de 10, 30, 100 et 300 échantillons. La dernière trajectoire est tronquée pour atteindre exactement le nombre d’échantillons voulu (cela signifie typiquement que pour les ensemble de 10 et 30 échantillons, l’expert ne fournit même pas une trajectoire complète). L’algorithme RelEnt ne fonctionnant pas avec uniquement des données de l’expert, un base d’entraînement supplémentaire D⇠ sas lui sera fournie. Cette base est constituée de 1000 trajectoires de longueur 5, débutant dans un état choisi au hasard uniformément dans tout l’espace d’état, les actions étant choisies également au hasard. Il est intéressant de noter que cette base contient d’un à deux ordres de grandeur plus d’échantillons que la base experte. Cette même base D⇠ sas sera utilisée par LSPI pour optimiser les récompenses trouvées par SCIRL et RelEnt. Les attributs utilisés par LSPI, SCIRL et RelEnt sont les mêmes, il s’agit d’un maillage de gaussiennes tel que décrit Équation 2.12 et illustré Figure 2.1. Le classifieur dont les performances sont illustrées est une SVM à noyau gaussien dont les hyper-paramètres sont choisis automatiquement par l’implémentation utilisée 7. Les performances de cette modèle étant très légèrement supérieures à celles du 7. Module SVM de Scikit-learn classifieur structuré de Taskar, Chatalbashev, Koller et Guestrin [Tas+05] (algorithme 1), ce sont celles que nous affichons ici. En ordonnée sur la Figure 5.1, nous représentons le nombre de pas nécessaire à l’agent pour qu’il atteigne le but (plafonné à 300), lorsque l’état de départ est tiré aléatoirement dans l’espace d’état entier. Les valeurs affichées sont la moyenne et l’écarttype sur 100 expériences. Ce critère est directement lié à la valeur de la politique pour la récompense inconnue RE : si l’expert touche une récompense de 1 lorsqu’il atteint l’objectif, et que la récompense est nulle partout ailleurs, du fait de l’amortissement temporel la valeur de sa politique en un état vaut gT où T est le nombre de pas qui le sépare de l’objectif. En conséquence, ce que nous traçons est le logarithme en base g de la valeur moyenne de la politique.
Perspectives de recherche
Les deux nouveaux algorithmes d’ARI que nous proposons disposent de garanties théoriques et une étude empirique illustre le fait qu’ils sont plus performants que les méthodes de l’état de l’art. Il serait souhaitable de renforcer cette étude empirique en les appliquant à d’autres problèmes, que ce soit des problèmes déjà résolus par d’autres méthodes, à des fins comparatives, ou des problèmes ouverts. Notamment, deux domaines ont commencé à être explorés, mais les travaux n’ont pu être menés à terme et de fait n’apparaissent pas dans ce manuscrit. Le premier est l’Arcade Learning Environment (ALE) : il s’agit d’un émulateur d’Atari 2600 permettant de jouer à une vaste collection de jeux vidéos. Le second est l’application d’algorithmes d’ARI à la commande d’un bras robot à partir de signaux issus d’une interface cerveau/machine (Brain Computer Interface, BCI) 4. Dans ces deux cas, la difficulté n’est pas dans l’application des algo- 4. Voir la section C.4 pour une description des travaux effectués sur la BCI. rithmes d’ARI eux-même, mais dans l’optimisation de la récompense qu’ils trouvent afin d’obtenir une politique de contrôle. Nous avons dans nos travaux considéré que cette étape ne posait pas problème, afin de nous concentrer sur le problème de l’ARI tel qu’envisagé par la communauté. L’application à des problèmes pratiques doit faire face à l’optimisation de la récompense, il faut alors faire appel à des méthodes de l’état de l’art en AR et des adaptations ad-hoc au problème (par exemple dans le choix des attributs). Pour remédier de manière plus générale à ce problème 5, nous pourrions également 5. Qui n’affecte pas les approches supervisées. tenter de développer un cadre pour les algorithmes d’ARI dans lequel l’optimisation finale de la récompense est simplifiée ou contournée. La politique de classification du classifieur paramétré par l’attribut moyen de l’expert qui constitue SCIRL est par exemple une bonne politique de départ pour un algorithme d’AR en ligne. Les données nécessaires à l’apprentissage de la politique de contrôle (dont SCIRL n’a pas besoin, grâce à son heuristique, pour trouver la récompense) pourraient alors être recueillies par la politique de classification, qui convergerait alors petit à petit grâce à l’algorithme d’AR en ligne vers la politique optimale pour la récompense trouvée par SCIRL. La politique issue de la première étape supervisée de CSI pourrait être utilisée de la même manière. Il est également possible de poursuivre l’approche envisagée dans [Gei+13a], consistant à instancier CSI avec une SVM et une SVR et à réunir les deux problèmes d’optimisation en un seul, dont la résolution permettrait d’obtenir directement une politique prenant en compte la structure de la récompense. Finalement, il faudrait intégrer l’AR et l’ARI dans des systèmes informatiques réels aux mains d’utilisateurs non qualifiés. Cela nécessitera sans doute d’importants travaux concernant l’intégration de multiples algorithmes dans un schéma hiérarchique : avant d’apprendre à un robot à faire un mojito, il faut qu’il apprenne à saisir un verre et une bouteille. Mais lorsqu’on lui apprend la recette, on ne veut pas avoir à se soucier des détails de la saisie manuelle d’objet, on fonctionne à un niveau d’abstraction plus élevé. Il faut donc qu’une politique par exemple “Saisir un verre” faisant appel à des actions telles que “Fermer doigt 1 de la main gauche” et “Tourner poignet gauche dans le sens direct” puisse être utilisée directement comme une action par une politique de plus haut niveau, à côté d’actions telles que “Piler la glace” et “Placer la rondelle de citron”. Il faudra également effectuer des progrès dans le domaine de l’interface homme/machine pour parvenir à gérer intuitivement des systèmes aussi complexes. Au-delà de l’aspect robotique grand public, les chercheurs et ingénieurs ont eux aussi beaucoup à gagner à manipuler intuitivement les machines, mais cela n’est pas facilement compatible avec la nécessité de rapidement changer de multiples paramètres.
|
Table des matières
Table des matières
Table des figures
Liste des tableaux
Liste des algorithmes
Liste des théorèmes et propositions
Acronymes
Notations
Anglicismes
1 Introduction
1.1 Motivations
1.2 Vue d’ensemble du manuscrit
2 Apprentissage par imitation
2.1 Imitation supervisée
2.1.1 Formalisme
2.1.2 Classification
2.1.3 Attributs
2.1.4 Classification à marge structurée
2.1.5 SVM
2.1.6 Imitation par apprentissage supervisé de la politique
2.2 Cadre des PDM pour la prise de décisions séquentielles
2.2.1 Dynamique temporelle
2.2.2 Récompense et valeur
2.2.3 Algorithmes d’AR
2.3 Définition de l’ARI
2.3.1 Définition du problème
2.3.2 Attribut moyen
3 Problématique de l’ARI et état de l’art
3.1 Fonction de récompense
3.1.1 Espace de départ
3.1.2 Reward shaping
3.2 Premières formulations du problème
4 edouard klein
3.3 Méthodes nécessitant la résolution répétée d’un PDM
3.4 Méthodes ne nécessitant pas la résolution répétée d’un PDM
4 Calcul de l’attribut moyen : LSTD-µ
4.1 Principe
4.2 Erreurs d’approximation
4.3 Avantages dans le cadre des approches existantes
4.4 Validation empirique
4.5 Conclusion
5 Classification structurée pour l’apprentissage par renforcement inverse
5.1 Liens entre classification et ARI
5.2 Description
5.2.1 Principe général
5.2.2 Instanciation avec heuristique
5.3 Validation théorique
5.4 Validation empirique
5.4.1 Introduction
5.4.2 SCIRL appliqué au mountain-car
5.4.3 SCIRL appliqué au highway
5.5 Conclusion
6 Apprentissage par renforcement inverse en cascadant classification et régression
6.1 Description
6.1.1 Principe général
6.1.2 Heuristique pour étendre CSI au cas où seules les données expertes sont disponibles
6.2 Validation théorique
6.3 Validation empirique
6.3.1 Introduction
6.3.2 CSI appliqué au mountain-car
6.3.3 CSI appliqué au highway
6.4 Conclusion
7 Conclusions et perspectives
7.1 Rappel des contributions
7.2 Perspectives de recherche
A Démonstrations
A.1 Borne sur la performance de SCIRL
A.2 Borne sur la performance de CSI
B Problèmes jouet
B.1 Problème du pendule inversé
B.2 Problème du mountain-car
B.3 Problème du highway
C Contributions
C.1 LSTD-µ
C.2 SCIRL
C.3 CSI
C.4 Autres travaux
Télécharger le rapport complet
