1

Reinforcement Learning

ParNicolas RichardJimmy Perron

2

Quiz

• Nommer :

• un des meilleurs joueur d’échec au monde

• un des meilleurs joueurs de BackGammon

• le contrôleur d’ascenseur le plus performant

• Une seule réponse Tous ces programmes

implémentent l’approche du Reinforcement Learning

3

Motivation

Développé dans les années 80

1. Simuler l’apprentissage animal (essais & erreurs)

2. Résoudre les problèmes d’optimisation dans les systèmes de contrôle

• Explosion combinatoire des états possibles

4

Plan

1. Problème

2. Éléments du Reinforcement Learning

3. Schéma général

4. Q-learning

5. Application

6. Limitation

7. Conclusion

5

1 - Problème…

6

2 - Éléments du RL

• Agent :• Apprend• Choisit des actions• Maximise sa récompense

• Environnement :• Définit les actions possibles• Attribue les récompenses

• État :• État de l’environnement à un moment t• Retourné à l’agent suite à une action

7

Plan

1. Problème

2. Éléments du Reinforcement Learning

3. Schéma général

4. Q-learning

5. Application

6. Limitation

7. Conclusion

8

3 - Schéma général

1. Environnement donne • L’état courant• Les actions possibles

2. Agent choisit• L’action

3. Environnement fournie• La récompense• L’état suivant• Actions possibles

9

3 - Schéma général

Agent

Environnement

Action

Récompense+

État t + 1

10

Notre exemple

•Environnement : •Carte de la ville

•État : •Une position particulière dans la carte

•Actions possibles : •Déplacement d’une case dans une direction légal

sa1

a2

S(s,a1) = s1’

S(s,a2) = s2’

11

Récompenses

• Attribution des récompenses (notre exemple) :Si S(s, a1) = but alors R(s, a1) = 100 sinon R(s, a1) = 0

100

00

• Lorsque le but est atteint :• Repositionnement de l’agent• Redémarrage du processus

12

Apprentissage

Maximiser ses récompenses

Apprendre à choisir la meilleure action

Attribuer une valeur caractérisant l’utilité d’une action Q( s, a )

13

Apprentissage

But100

10090

81

90

81

81

72

7281

8190

Environnement

Agent

Récompense

Q( s, a )

But100

0

0

0

0

0

14

Plan

1. Problème

2. Éléments du Reinforcement Learning

3. Schéma général

4. Q-learning

5. Application

6. Limitation

7. Conclusion

15

4 – Q-Learning

Algorithme

Pour chaque paire ( s, a ), mettre Q( s, a ) à 0

Observer l’état courant s

Faire pour toujours

A. Choisir une action a et l’exécuter

B. Recevoir la récompense

C. Observer le nouvel état s’

D. Mettre à jour la valeur de Q( s , a )

16

A - Choisir l’action à exécuter

• Hasard ?

• L’action ayant la valeur de Q maximale ?• Maximum local

• Combinaison des deux approches ?• Exploration ou exploitation ?• Probabilité d’une action pondérée selon Q

17

A – Choisir l’action à exécuter

Probabilité de choisir une action ai dans unétat s

P(ai | s) = KQ(s, ai)

j KQ(s, aj)

Si k = 1 Choix équiprobableSi k > 1 Favorise les actions ayant un Q élevéSi k < 1 Favorise les actions ayant un Q peu élevé

18

B – Recevoir la récompense

Algorithme

Pour chaque paire ( s, a ), mettre Q( s, a ) à 0

Observer l’état courant s

Faire pour toujours

A. Choisir une action a et l’exécuter

B. Recevoir la récompense

C. Observer le nouvel état s’

D. Mettre à jour la valeur de Q( s , a )

19

C – Observer le nouvel état s’

Algorithme

Pour chaque paire ( s, a ), mettre Q( s, a ) à 0

Observer l’état courant s

Faire pour toujours

A. Choisir une action a et l’exécuter

B. Recevoir la récompense

C. Observer le nouvel état s’

D. Mettre à jour la valeur de Q( s , a )

20

D – Mettre à jour Q( s, a )

Algorithme

Pour chaque paire ( s, a ), mettre Q( s, a ) à 0

Observer l’état courant s

Faire pour toujours

A. Choisir une action a et l’exécuter

B. Recevoir la récompense

C. Observer le nouvel état s’

D. Mettre à jour la valeur de Q( s , a )

21

D - Mettre à jour Q( s, a )

• Affecter à Q la valeur de la récompense ?

– Persistance de l’information

• Moyenne des 10 dernières récompenses ?

– Plus de précision explosion de l’espace

mémoire

22

D - Mettre à jour Q( s, a )

• Fonction Q :

Q( s, a ) r + Maxa’ ( Q( s’, a’ ) )

Où

– r = récompense reçue

= Constante de propagation temporelle ( 0 < < 1)

– Maxa’ ( Q(s’ , a’) )

23

Plan

1. Problème

2. Éléments du Reinforcement Learning

3. Schéma général

4. Q-learning

5. Application

6. Limitation

7. Conclusion

24

Exemple : La Sim

• L’agent vs l’environnement

• Illustration du choix de l’action

• Illustration de l’atteinte d’un but (mise a jour de Q)

• Convergence de Q

• Variation de k

– Tester avec 10 000 itérations avec k = 1.01 et k = 10

– Équilibre entre :

• Certain de la connaissance sans avoir tout exploré

• Moins certain de la connaissance mais elle soit répandue

25

Plan

1. Problème

2. Éléments du Reinforcement Learning

3. Schéma général

4. Q-learning

5. Application

6. Limitation

7. Conclusion

26

6 – Limitations

• Apprentissage supervisé ?

• Besoin de beaucoup d’exploration

– Pas de connaissance préalable du domaine

– La connaissance n’est pas transportable

– Adapté à l’environnement immédiat

27

6 – Limitations

• Le concept taux d’erreur est innaplicable

• Difficile de calculer le taux de confiance

• Adaptation des connaissances mais :

– C’est long!!!

• Aucune généralisation de l’apprentissage

28

Critiques

• Utilisation– Environnement réactif– Comparaison avec le « version space »

• Possible mais…inopportun

– Bien adapté pour les jeux de société

29

Conclusion

• Ni blanc, ni noir

– Dépend beaucoup du problème

– Apprentissage non supervisé

– Besoin de beaucoup d’itérations

• Apprentissage d’une fonction d’évaluation (exemple la fonction Q)

• Pas de généralisation de cette fonction