Apprentissage par Renforcement Processus Décisionnels de Markov
11
pages
Catalan
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
11
pages
Catalan
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Apprentissage par Renforcement
Processus D´ecisionnels de Markov
Alain Dutech
Equipe MAIA - LORIA - INRIA
Nancy, France
Web :http://www.loria.fr/~dutech
Mail :Alain.Dutech@loria.fr
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? ...
Voir
Processus D´ecisionnels de Markov
Alain Dutech
Equipe MAIA - LORIA - INRIA
Nancy, France
Web :http://www.loria.fr/~dutech
Mail :Alain.Dutech@loria.fr
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? ...
Apprentissage par Renforcement
Processus D´ecisionnels de Markov
Alain Dutech
Equipe MAIA - LORIA - INRIA
Nancy, France
Web :http://www.loria.fr/~dutech
Mail :Alain.Dutech@loria.fr
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
