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
✓ 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 ?
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
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
• 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
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
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
➤ 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.
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'
➤ 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