Apprentissage par Renforcement Processus Décisionnels de Markov

Alain Dutech

Sujets

• Recco
• Modification post-transcriptionnelle
• D'une ombre à l'autre
• Banque d'Estonie
• Maison départementale des personnes handicapées
• Univers de Harry Potter

Informations

• Publié par: Seym
• Nombre de lectures: 80
• Langue: Catalan

Extrait

Apprentissage par Renforcement Processus D´ecisionnels de Markov Alain Dutech Equipe MAIA - LORIA - INRIA Nancy, France Web :http://www.loria.fr/~dutech Mail :[e-mail] 13 janvier 2007 Introduction Form Apprendre Conclusion Des exemples inspirants? I Animal apprenant `a trouver de la nourriture en ´evitant des pr´edateurs I Robot qui apprend `a trouver sa station d’accueil pour se recharger I Un programme qui apprend `a jouer au backgammon I Une ´equipe de foot qui essaye de trouver des stat´egies pour marquer des buts I Un drone h´elicopt`ere apprenant `a voler sur le dos I Un enfant apprenant `a se servir d’une cuill`ere I Un bras articul´e essayant de faire tenir une baguette en ´equilibre I Un rat qui apprend `a appuyer sur le bon bouton pour recevoir de la nourriture. I ... Page 2Introduction Form Apprendre Conclusion Diff´erent modes d’apprentissage modif modif 2˜Y RecE = (Y −Y )i ti i i Apprentissage ˜X ClassYi iiArtificiel I Apprentissage Supervis´e On doit connaˆıtre exactement la valeur de la sortie d´esir´ee. On apprend en utilisant l’erreur exacte commise. I Apprentissage par Renforcement Une indication de la qualit´e d’un choix. On n’a pas besoin de connaˆıtre le choix exact `a faire. I Apprentissage Non-Supervis´e Que des entr´ees, on travaille sur les corr´elations et les similarit´es de ces donn´ees. Page 3 Introduction Form Apprendre Conclusion Agent apprenant S2 Rec. +5Env S1 Action?? action (observation, récompense) Rec. -2 B S S3 n Action?? (comportement) Page 4Introduction Form Apprendre Conclusion Comment faire concr`etement? Prenons un exemple concret : Je suis dans l’´etat : 34, je re¸cois : 0, je choisi l’action :1. ” 43, ” 1, ” 4. ” 17, ” 0, ” 3. ” 34, ” 0, ” 1. ” 23, ” 20, ” 2. ” 21, ” -1, ” 2. ” 43, ” 0, ” 2. ” 22, ” 10, ” 3. Question Comment automatiser le processus permettant d’apprendre `a choisir une bonne action? Page 5 Introduction Form Apprendre Conclusion Evaluer des choix I Comment savoir si une action, ou une s´equence d’action est un bon choix? (“delayed reward”, “credit assignement”) I → Crit`eres de performance s’appuyant sur la r´ecompense P N−1 I le crit`ere fini : E[ r ].tt=0 P∞ t I le crit`ere γ-pond´er´e : E[ γ r ]tt=0 P n−11 I le crit`ere moyen : lim E[ r ]n→∞ tn t=0 Page 6Introduction Form Apprendre Conclusion Formalisme : Processus de D´ecision Markovien D´efinition d’un MDP MDP =hS,A,p(),r()i ou` : IS : ensemble d’´etats IA : ensemble d’actions I p(s ,a ,s ) = Pr(s |s ,a ) : transitionst t t+1 t+1 t t I r(s,a) : r´ecompenses R´esoudre un MDP Trouver des politiques π :S −→4(A) qui maximisent l’esp´erance du crit`ere de r´ecompense sur le long terme. Page 7 Introduction Form Apprendre Conclusion Fonction Valeur Concept essentiel, le but ´etant d’estimer la “qualit´e” d’un ´etat. ∞X π tV (s) = E[ γ r|s = s] (1)t 0 t=0 Equation de Bellman X π 0 π 0V (s) = r(s)+γ{ p(s,π(s),s )V (s )} (2) 0s ∈S Rem : la fonction valeur d´epend de la politique choisie π. A quoi ca¸ sert? Page 8Introduction Form Apprendre Conclusion Calculer la fonction valeur d’une politique π On peut r´esoudre le syst`eme suivant : X 0 0V(s) = r(s,π (s))+γ Pr(s | s,π (s))V(s ), ∀s∈Sn n 0s ∈S ou utiliser une m´ethode (approximative) it´erative Entr´ee : π∈4(A); V (s)∈R; n← 0; ∈R;0 1: repeat 2: for s∈S do P 0 03: V (s)← r(s,a)+γ Pr(s | s,π(s))V (s )0n+1 ns ∈S 4: end for 5: n← n+1 6: untilk V −V k