COURS-1-2000
17 pages
Catalan
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
17 pages
Catalan
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

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 ...

Informations

Publié par
Nombre de lectures 38
Langue Catalan

Extrait

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
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents