Apprentissage pour la prise de décision

Nous allons adapter le principe de la carotte et du bâton à l'ordinateur. Pour ce faire, on observe à chaque cycle l'évolution de la situation. En fonction de celle-ci nous attribuerons ou non une récompense. Le but du programme d'apprentissage est alors de maximiser les récompenses obtenues, c'est à dire d'adopter un comportement, de réaliser les actions qui apportent une récompense, soit, les actions qui rapprochent du but.

A partir de la description de l'environnement, on commence par déterminer la situation où l'on se trouve. Connaissant toues les actions possibles pour cette situation, on choisit la plus prometteuse.
Comment déterminer l'action la plus prometteuse ? A chaque couplet situation-action possible (que nous nommerons maintenant règle, qui peut s'exprimer par : SI Situation = A Alors Action = 8), on attribut une force. Cette force sera le produit de l'historique des récompenses reçues lorsque la règle en question est utilisée. Elle est altérée par la valeur de la récompense reçue :

• soit R_S,A(t) la force de la règle Si S Alors A à instant t. Supposons que cette règle soit choisie à l'instant t+1, et soit R la valeur de la récompense obtenue.
• Alors R_S,A(t+1) = aR_S,A(t)+(1-a)R, a E [0;1].

S'il y a récompense (R non nul) la force augmente, sinon elle diminue. On attribut également un poids à toute règle. La somme des poids est constante et également répartie sur toutes les règles au départ.
Ces poids vont traduire l'utilisation des règles indépendamment de leur force. Quand une règle est utilisée on augmente sont poids (tout en diminuant le poids d'une autre règle, la moins forte, pour conserver la somme des poids constante). Ainsi plus une règle est forte, plus elle aura de chances d'être utilisée, et donc plus son poids risque d'augmenter. La connaissance du poids et de la force de chaque règle va permettre, à chaque itération de choisir une action.

Une interprétation possible de ce fonctionnement est l'algorithme génétique [Hol 75]. L'individu a pour code génétique une règle et pour force, celle de la règle telle qu'elle vient d'être présentée. Le poids devient l'effectif de l'individu dans la population de taille fixe (la taille de la population est donc égale à la somme des poids). Lors de l'utilisation d'une règle, on duplique alors l'individu correspondant dans la population et on élimine un représentant de la plus mauvaise règle. Dans ce cas de figure, c'est l'opérateur de sélection de l'algorithme génétique qui choisi l'action à effectuer.

Pour de grands nombres de situations et d'actions possibles, le nombre de règles devient vite très important. Il est alors possible de généraliser les règles afin de réduire leur nombre. Si pour deux situations A et B, l'action 5 est très efficace, il peut être judicieux de remplacer les règles Si A alors 5, et Si B alors 5, par Si A ou B alors 5.

De plus, si l'apprentissage est fondé sur un algorithme génétique il n'est pas nécessaire d'avoir un représentant de chaque règle possible. Les capacités d'exploration propres à ce type d'algorithme par le biais du croisement et de la mutation permet de générer constamment de nouvelles règles. Si cela fonctionne très bien sur des problèmes simulés, mais pour un problème concret comme le nôtre il faudrait pouvoir évaluer très rapidement les règles, c'est à dire sans réaliser toutes les actions qu'elles impliquent.

Comme le nombre de règle dans notre cas n'est pas trop important et ces procédés d'induction [Col 96] ne seront plus abordés.

Connaissant la situation S du système, il nous faut maintenant choisir la bonne action. Cette décision peut se faire selon l'une des trois stratégies suivantes à l'aide de la force des règles possibles (celles dont S est la condition) et éventuellement à l'aide de leur poids.

• On note :
  • P(i) = Probabilité de choisir l'action i,
  • R_S,i = force de l'action i pour la situation S,
  • P_S,i = poids de l'action i pour la situation S.
• Stratégie 1 :
  • Soit
  • P(j) = 0.9 et P(i) = i,j
• Stratégie 2 :
  • Pour chaque action j : P(j) =
• Stratégie 3 :
  • Pour chaque action j : P(j) =
  Pour cette stratégie les poids ont une grande influence, et afin que chaque règle conserve une probabilité d'être choisie (et conserver une possibilité d'exploration), ils ne pourront pas être nuls.

Selon le fonctionnement décrit dans le premier paragraphe de ce chapitre, une récompense est attribuée à chaque itération et le force de la dernière règle utilisée n'est fonction que de cette rétribution. La force peut être vue comme une probabilité de recevoir une bonne récompense se basant sur les expériences antérieures (attention ce n'est qu'une interprétation et non une vérité mathématique). Quand l'ordinateur utilise une règle de force 0.72, il espère à 72 % (nos récompenses sont toujours comprises entre 0 et 1 inclus, les forces le sont donc également) que l'action sera un succès, i.e. qu'elle va générer une récompense.

Pourtant, il est parfois préférable de choisir une action moins gratifiante, mais qui permet d'atteindre une situation plus avantageuse (en présence d'obstacles notamment). Nous n'allons donc plus donner une récompense à chaque itération mais la retarder toutes les n actions effectuées. Quand aucune récompense n'est attribuée, la force de la dernière règle choisie est ajournée en fonction de la prochaine règle choisie. Le système va alors apprendre des enchaînements d'action au lieu d'agir coup par coup.

Le Q-learning [ref ??] propose lui d'ajourner la dernière règle choisie avec la force de la meilleure règle conditionnée par la situation atteinte. La force attribuée n'a par conséquent plus du tout la même signification et traduirait plutôt une probabilité d'atteindre une situation plus avantageuse.

Il est important de comprendre que la force n'exprime pas la même chose d'une méthode à l'autre (cf. exemples au paragraphe 3.6.2). Cette différence explique les comportements spécifiques observés pour chacune de celles-ci.

Voici maintenant l'algorithme dit du bandit manchot, étendu au principe des récompenses retardées.

• Observer la situation : S
• Choisir l'action initiale : A (au hasard)
• Tant que le but n'est pas atteint faire :
  • Effectuer l'action A (transmettre l'ordre d'agir au robot)
  • Dupliquer l'action effectuée, i.e. si possible augmenter son poids de 1 et diminuer celui de la moins forte action pour cette situation.
  • Observer la nouvelle situation : S' (dans notre cas, déterminer S' en fonction de la liste d'objets fournie par la perception)
  • Choisir la prochaine action : A'
  • Toutes les n actions faire :
    • Si Amélioration de la situation Alors
      • R := 1
      Sinon
      • R := 0
    • 
    Sinon faire :
    • Si Q-learning Alors
      • 
      Sinon
      • A'' := A
    • 
  • A := A'
  • S := S'
  Fin tant que

La manière dont les forces évoluent et donc l'efficacité de l'algorithme dépendent fortement du paramètre alpha :

• Si alpha = 1, les forces n'évoluent plus et la machine n'apprend rien.
• Si alpha = 0, les forces sont égales à la récompense reçue lors de la dernière utilisation de la règle correspondante. L'algorithme ne tient plus compte de son histoire.

Pour la suite nous avons fixé alpha = 0.8

Que se passe-t-il, lorsqu'on utilise la troisième stratégie de décision (cf. paragraphe 3.2), si une règle très efficace tout au long d'un long apprentissage devient tout à coup complètement inefficace ?

Jusqu'à ce changement des propriétés de l'environnement (la réponse aux actions n'est plus celle attendue), la règle en question bénéficiait d'un poids maximal et d'une force très élevée. Pour que le système soit de nouveau capable, il doit réapprendre : réajuster force et poids. Il faudra beaucoup de temps pour que la force baisse suffisamment pour rendre cette action défaillante moins probable que les autres. Il peut alors se révéler judicieux de détecter ce problème plus tôt. Pour cela, quand une action échoue, on examine force et poids pour voir s'ils sont en contradiction. Une règle faible ne doit pas être utilisée, son poids doit donc être également faible. Si on observe alors un poids fort, pour une force peu élevée, on redistribue le poids sur les autres règles ayant la même condition, i.e. celles correspondant à la même situation.

Pour mettre au point ces algorithmes et décider des paramètres, nous avons bâti une simulation qui sera le support du système final (il suffira d'adapter l'observation et l'action). Cette simulation est disponible sur la disquette jointe (\learn\apprent.exe).