COURS-1-2000
17
pages
Catalan
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
17
pages
Catalan
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
29I. L’apprentissage: généralités– Définition, exemples illustratifs, motivations, historiqueII. Construire un système d’apprentissageIII.L’apprentissage par renforcementIV. Exemple illustratif (TD)© J-D. ZUCKER LIP630III. Apprentissage par renforcement: situationEnvironnementPerceptionRécompenseAction✓Agent autonome✓Apprentissage en ligne✓Apprentissage modifie l'env.✓Monde peut être non déterministe© J-D. ZUCKER LIP631III.1. Apprentissage par renforcement (définition)Apprentissage par renforcement (ou interaction)But: (Apprendre à) prendre la meilleure action dans une situation SiL'environnement donne une récompense r pour une action a dans l'état S (ouipour une séquence d'actions)Origine: apprentissage des animaux (par exemple souris)Aujourd'hui: de l'essai-erreur à la planification controlée≠ Apprentissage supervisé:un professeur dit la bonne action à prendre en Si(par exemple: dans la position S il faut jouer sur la case 33)i© J-D. ZUCKER LIP632Pourquoi apprendre par renforcement ?• Le signal d'un professeur est rarement disponible• Une récompense est plus facile à spécifier qu'un comportement:+ for removing dirt- for consuming energy- - for damaging furniture- - - for terrorizing cat© J-D. ZUCKER LIP633I.2. Exemples illustratifs ✓ Les jeux (dans certains cas): jugements intuitifs, blitz...✓ A la naissance, une gazelle tient à peine debout...✓ Attraper son paquet de céréal favori, un ballon,...✓ Stratégie d'un robot (se ...
Voir
Publié par
Langue
Catalan
I. L’apprentissage: généralités – Définition, exemples illustratifs, motivations, historique II. Construire un système d’apprentissage
III. L’apprentissage par renforcement
IV. Exemple illustratif (TD)
III. Apprentissage par renforcement: situation
Environnement
Récompense
Perception Action
29
© J-D. ZUCKER LIP6
30
✓ Agent autonome ✓ Apprentissage en ligne ✓ Apprentissage modifie l'env. ✓ Monde peut être non déterministe © J-D ZUCKER LIP6 .
III.1. Apprentissage par renforcement ( définition )
Apprentissage par renforcement (ou interaction) But : (Apprendre à) prendre la meilleure action dans une situation S i L'environnement donne une récompense r pour une action a dans l'état S i (ou pour une séquence d'actions) Origine : apprentissage des animaux (par exemple souris) Aujourd'hui : de l'essai-erreur à la planification controlée ≠ Apprentissage supervisé: un professeur dit la bonne action à prendre en S i (par exemple: dans la position S i il faut jouer sur la case 33)
Pourquoi apprendre par renforcement ?
• Le signal d'un professeur est rarement disponible • Une récompense est plus facile à spécifier qu'un comportement: + for removing dirt - for consuming energy - - for damaging furniture - - -for terrorizing cat
31
© J-D. ZUCKER LIP6
32
© J-D. ZUCKER LIP6
I.2. Exemples illustratifs
✓ Les jeux (dans certains cas): jugements intuitifs, blitz... ✓ A la naissance, une gazelle tient à peine debout... ✓ Attraper son paquet de céréal favori, un ballon,... ✓ Stratégie d'un robot (se recharger)/(continuer) ✓ Contrôleurs adaptatifs temps réel (prod./coût/qualité) ✓ Equilibre
✓ Point communs: ✓ intéractions, sous-buts, incertitude de l'environnement. ✓ l'expérience permet d'apprendre ...
Exemple 1: Le problème du "bandit à k bras" p1=? p2=? p3=? 011
Bandit 1
Bandit 2
Bandit 3
.......
Il y a k machines à sous Chacune donne 0 ou 1 avec une loi de probabilité cachée On peut jouer h coups. Comment choisir les machines pour optimiser le gain ?
33
© J-D. ZUCKER LIP6
pk=? 0
Bandit k
34
© J-D. ZUCKER LIP6
Exemple 2: Le jeu de Tic-Tac-Toe
Soit
35
© J-D. ZUCKER LIP6
Apprentissage par renforcement: • On apprend la valeur des positions en fonction des parties jouées.
✔ On ne sait pas quelle récompense attribuer à quelle action credit assigment problem
• Un TicTacToe à 9 cases • Comment apprendre à évaluer une position ?
Apprentissage Supervisé: • Un ensemble de couple (positions notes):
I.4. Quand doit-on faire appel à l'app. par renf. ?
36
✔ La récompense peut venir plus fréquemment (perdre une pièce aux échec) mais celle-ci ne donne pas d'indication sur la solution optimale e.g. Prise de pièces (attention un sacrifice peut mener à la victoire)
✔ Une tâche en plusieurs étapes où la récompense ne vient qu'à la fin d'une succession de choix (un état final) e.g. Recherche dans un labyrinthe
- ZUCKER LIP6 .
, 10
37
II.1. Deux types d'approche pour apprendre π A) Apprendre V π la fonction d'utilité liée aux états (TD-learning) Dans l'état S i choisir l'action a qui maximise l'utilité V(S i+1 ) supposée de l'état S j+1 obtenue après avoir fait l'action a . Requiert un modèle assez précis de l'environnement pour connaître les états où mènent les actions ( exemple: Jeux de dame+Minimax)
B) Apprendre Q π la fonction d'utilité liée aux actions (Q-learning) Choisir l'action a qui maximise Q( S i ,a) : l'utilité supposée de l'action a dans l'état S i Requiert un modèle limité de l'environnement: on n'a besoin que de mesurer la valeur d'une action et non l'état résultant de l'action (pas de look-ahead) ( exemple: attraper une plume, blitz )
Modèlisation: états, actions et récompenses
r(s,a) récompense immédiate (inconnue au départ)
0 100 But0 0 0 0 0 0 100 0 0
0 0
➤ Dernière étape qui assure la récompense (jeux, monde des blocs, etc.) ➤ Tâche: apprendre la meilleure stratégie qui maximise le gain
© J-D. ZUCKER LIP6
38
© J-D. ZUCKER LIP6
Critères de gains ➤ Horizon fini k ∑ r t = r 0 + r 1 + ... + r k t = 0 ➤ Horizon infini avec intérêt ∞ ∑ γ t = 0 + γ 1 + γ 22 + γ 33 + ... r t r r r r t = 0
➤ En moyenne
1 k r l k i → m ∞ k t = ∑ 0 t
Comparaison des comportements k=4, γ =0.9 Quelle est la meilleure stratégie
+2
+10
k ∑ r t t = 0 6
0
+11 0
39
© J-D. ZUCKER LIP6
40 t =∞ ∑ 0 γ t r t k li → m k 1 t ∑ k r t ∞= 0 16.0 2
59.0 10
58.4 11
© J-D. ZUCKER LIP6
Récompense Cumulée ∞ ➤ On définit la récompense cumulée V π (s t ) = ∑ γ t r t π t = 0 ➤ Le problème: trouver π * = argmax( v (s)) π
90
81
100
90
V*(s)=V π * (s) récompense cumulée optimale
Une stratégie
• Apprendre une fonction Q: Q : S × A → valeur • L'utiliser pour choisir la meilleure action π ( s ) = argmax Q ( s , a ) a ∈ A
But0
100
41
© J-D. ZUCKER LIP6
© J-D. ZUCK
42
RE LIP6
• Mais si P et R sont inconnus... il faut apprendre une politique
© J-D. ZUCKER LIP6
• Propriété de Markov P ( s t | s t − 1 , a t − 1 ) = P ( s t | s t − 1 , a t − 1 , s t − 2 , a t − 2 , ...) • Alors Q ( s , a ) = R ( s , a ) + γ ∑ P ( s ′ | s , a ) max Q ( s ′ , a ′ ) ′ s ′∈ S a ∈ A
récompense taux prochain état Valeur future immédiate d'intérêt espéré • Theorem: Etant donné P et R, il y a une unique Q [Bellman]
43
Processus de décision Markovien
10
• Si vous avez confiance en vous: – choisissez π ( s ) = argmax Q ( s , a ) • Sinon, a ∈ A – explorez
• Exploration versus exploitation:
44
Choix d'une action
??
© J-D. ZUCKER LIP6
Trouver un algorithme: problèmes BUT : Trouver une politique π : S --> A, qui à tout état s t associe l'action a t qui optimise un critère de gain . ➤ "Temporal Credit Assignment": quelles sont les actions qui doivent être créditées ? ➤ Exploration/exploition: quel compromis avoir ? ➤ Etats partiellement observables : si les capteurs ne donnent pas toutes les infos ? ➤ Apprentissage à long terme: ré-utiliser des connaissances apprises pour d'autres taches ? Performances: vitesse de convergence, regret
45
© J-D. ZUCKER LIP6
Quelle fonction apprendre ? ➤ La politique optimale π * ? ➤ pas d'exemples de la forme (s,a) ➤ La récompense cumulée V* ? ➤ L'agent choisira alors s1 plutôt que s2 car V*(s1) > V*(s2) et comme il faut choisir une action. π * ( s ) = argmax(r(s,a) + γ V *( δ (s,a))) a ➤ Intéressant ssi r(s,a) et δ (s,a) sont totalement connues
46
➤ La fonction Q ci-dessous offre une réponse ➤ On définit Q(s,a)= r(s,a) + γ V*( δ (s,a)) ➤ Point clef: l'agent pourra prendre les décisions optimales sans connaissances des fonctions r(s,a) et δ (s,a) © J-D. ZUCKER LIP6
La "beauté" de la fonction Q
➤ La fonction Q est définit comme étant LA fonction qui résume en UN nombre toute l'info nécessaire sur le gain cumulé d'une action a, prise dans l'état s.
Q(s,a)
90 100 But 81 0 72 81 81 90 100 81 90 72 81
47
© J-D. ZUCKER LIP6
48
III. Un algorithme pour apprendre Q(s,a) (cas déterministe) Q(S,a)=r(s,a) + γ V*( δ (s,a)) ➤ On a : V * ( s ) = m a ' ax Q(s,a' ) ➤ Définition récursive: Q ( s , a ) = r ( s , a ) + γ m a ' ax Q( δ (s,a),a' ) ^ Pour chaque couple s, a initialisé la table Q(s,a) à zéro. Pour l'état courant s Répéter
Choisir une action a et l'exécuter ( exploration vs. exploitation ) Réception d'une récompense immédiate r Observer le nouvel état s' ∧ ∧ MAJ de Q ( s , a ) ← r ( s , a ) + γ ma ' x Q ( δ (s,a),a') a s <-- s'
© J-D. ZUCKER LIP6
Exemple illustratif... On Prend γ =0.9
∧ ∧ Q s , a ) ← r + γ Q ) ( m a ' ax ( δ (s, a),a' ) ← 0 + 0.9m ax { 63,81,100 } } ← 90
Convergence
72 100 63 81
a droite 90 100 63 81
^ Q(s,a)
^ Q(s,a)
49
© J-D. ZUCKER LIP6
➤ Théorème: convergence de l'algo Q-learning déterministe ^^ ➤ Soit Q n (s,a) l'hypothèse de Q(s,a) après la n ième mise à jour. ➤ Si chaque couple (état,action) est visité un nombre infiniment souvent, alors Q n (s,a) converge vers Q(s,a) quand n tend vers l'infini. ➤ Démonstration Q ∧ n s a Q s a ∆ n ≡ m s , a a x ( , ) − ( , ) ∧ ∧ Q n + 1 ( s , a ) − Q ( s , a ) = ( r + γ m ' ax Q n ( s ' ,a' )) - ( r + γ m ' ax Q ( s ' ,a' )) a a ∧ ∧ Q n + 1 ( s , a ) − Q ( s , a ) = γ m ' ax Q n ( s ' ,a' ) − ma ' x Q ( s ' ,a' ) a a ∧ ∧ Q n + 1 ( s , a ) − Q ( s , a ) ≤ γ ma ' x Q n ( s ' ,a' ) − Q ( s ' ,a' ) a ∧ ∧ Q n + 1 ( s , a ) − Q ( s , a ) ≤ γ ma ' x Q n ( s ' ' ),a' ) − Q ( s ' ' ,a' ) s , a ∧ Q n + 1 ( s , a ) − Q ( s , a ) ≤ γ ∆ n
© J-D. ZUCK
50
REL PI6
