Cette page concerne la partie « Agents adaptatifs ; prise de décision séquenielle » du cours intitulé « Complexité et algorithmique du renforcement ». Jean-Paul Delahaye en assure l'autre moitié.

Quand : jeudi matin, 10h15-12h15, à partir du 29 octobre 2009, amphi Turing, bâtiment M3.

Planning de l'ensemble du cours :

• Jean-Paul Delahaye : du jeudi 18/9/2008 au jeudi 22/10/2008
• Philippe Preux : du jeudi 29/10/2009 au jeudi 3/12/2008 (pas de séance le 5 octobre).

Objectifs de ce module

L'objectif de ce cours est de réflêchir sur la notion d'agents adaptatifs et d'examiner les problèmes posés, les solutions existantes, et discuter les problèmes qui restent ouverts.

L'expression « agent adaptatif » représente un agent informatique :

• situé dans un environnement qu'il perçoit,
• sur lequel il agît, ce qui implique des changements, donc une évolution de son environnement au cours du temps,
• dont les actions sont suivies de conséquences,
• qui a un but à atteindre,
• qui doit apprendre comment atteindre cet objectif, au mieux.

Les exemples sont très nombreux : imaginez un agent qui apprend :

• à jouer à un jeu (jeu vidéo (pacman, tétris, ...), jeu de plateau (échecs, dames, go, ...), jeu d'aventures, ...) ;
• à commander un robot (une voiture, un drone, ...) ;
• à gérer une organisation (coordonner la distribution de paquets dans une entreprise de messagerie, une chaîne de montage, l'envoi de catalogues, ...) ;
• à optimiser les ventes sur un site web marchand ;
• à optimiser le revenu d'un portefeuille boursier 
• ...

L'agent s'adapte au cours du temps ; aussi, il s'agît d'un processus qui se déroule au cours du temps ; à chaque instant, l'agent doit décider de l'action à effectuer (décider) en tenant compte de ce qui lui est arrivé précédemment, d'où la dénomination de « prise de décision séquentielle » d'une manière générale.

L'agent en question peut être virtuel ou matériel (un robot physique) ; l'environnement peut lui aussi être virtuel (dans un ordinateur, le web, ...), ou physique.
Selon les informations dont on dispose sur l'environnement et son évolution au cours du temps, différentes approches ont été développées :

• l'agent connaît les conséquences de ses actions sur l'environnement et celles-ci ne changent pas au cours du temps ; il reste alors à trouver la meilleure séquence d'actions l'amenant de son état courant à son état final lorsqu'il a atteint son objectif. C'est un problème de planification.
• l'agent ne connaît pas ces connaissances : il doit les apprendre tout en cherchant à atteindre son objectif.
• l'agent connaît exactement ou pas l'état courant de son environnement

Dans tous les cas, l'agent doit apprendre comment interagir avec son environnement : il est important de bien réaliser que l'on ne s'intéresse pas à des agents qui auraient une base de connaissance leur explicitant comment atteindre leur objectif. On suppose que la manière d'atteindre l'objectif est a priori inconnue et que l'agent doit découvrir comment l'atteindre.

Concernant l'environnement, celui-ci est non déterministe (stochastique) : les conséquences d'une action de l'agent peuvent être aléatoires. La perception de l'environnement par l'agent est par ailleurs incertaine.

L'intérêt d'une approche incrémentale est que l'agent adapte constamment son comportement à son environnement ; donc, si l'environnement change, le comportement de l'agent va s'y adapter de lui même.

Durant le cours, on présentera ce problème de décision séquentielle d'une manière générale et on se concentrera sur quelques cas particuliers importants. On verra les méthodes actuellement utilisées pour résoudre ces différentes variantes problèmes ; on verra comment on aborde un problème concret. À côté du cours, chacun est vivement invité à implanter les algorithmes qui seront vus en autonomie.

Pré-requis

Typiquement, une première année de master en informatique, laquelle s'appuie sur quelques années de mathématiques après le bac (licence ou prépa).

• en informatique :
  • maîtriser un langage de programmation quel qu'il soit, mais C est le langage préféré ;
  • savoir implanter un algorithme, débugger le programme, ...
• en mathématiques (ces notions de maths utiles au cours seront revues de manière informelle) :
  • notions de probabilités : variable aléatoire, loi de probabilité (uniforme, normale), loi de Bayes
  • notions de statistiques : moyenne, variance, biais d'un estimateur, intervalle de confiance, test statistique
  • notions d'analyse : dérivabilité, dérivée d'une fonction, intégrale, ...
• et surtout, avoir envie de comprendre, d'apprendre, être curieux, ...

Plan du cours

• introduction au cours illustré avec des exemples d'applications
• définition du problème d'apprentissage par renforcement
• les algorithmes de la différence temporelle
• l'approximation de fonction en-ligne
• algorithme de recherche directe d'une politique

Contrôle de connaissances

10 décembre 2009, 10h15-12h15.
Il comportera deux parties, l'une sur le cours de J-P. Delahaye, l'autre sur la mienne ; chacune est calibrée pour une heure de travail. Tous les documents papiers sont autorisés.

Équipe de recherche associée

Si ce cours vous a plu et que vous cherchez à effectuer un mémoire sur ce type de problématiques, vous pouvez essayer de rejoindre l'équipe SequeL de l'INRIA-Futurs à Lille et du LIFL.

Mémoires proposés en 2010 :

• Optimisation de l'affichage de bandeaux publicitaires sur un portail web
• Apprentissage automatique et qualité du logiciel

Quelques références et liens

• Support de cours
• les concepts et méthodes d'apprentissage automatique sont très utiles pour ce cours ; on pourra lire mes notes de cours de fouille de données

Retour à ma page web.