Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Apprendre Implémentations Incrémentales | Méthodes de Monte Carlo
Introduction à l'Apprentissage par Renforcement
course content

Contenu du cours

Introduction à l'Apprentissage par Renforcement

Introduction à l'Apprentissage par Renforcement

1. Théorie Fondamentale de l'Apprentissage par Renforcement
2. Problème du Bandit Manchot
3. Programmation Dynamique
4. Méthodes de Monte Carlo
5. Apprentissage par Différence Temporelle

book
Implémentations Incrémentales

Stocker chaque retour pour chaque paire état-action peut rapidement épuiser la mémoire et augmenter considérablement le temps de calcul — en particulier dans des environnements de grande taille. Cette limitation affecte aussi bien les algorithmes de contrôle Monte Carlo on-policy qu'off-policy. Pour y remédier, nous adoptons des stratégies de calcul incrémentiel, similaires à celles utilisées dans les algorithmes multi-armed bandit. Ces méthodes permettent de mettre à jour les estimations de valeur à la volée, sans conserver l'historique complet des retours.

Contrôle Monte Carlo On-Policy

Pour la méthode on-policy, la stratégie de mise à jour ressemble à celle utilisée dans les algorithmes MAB :

Q(s,a)Q(s,a)+α(GQ(s,a))Q(s, a) \gets Q(s, a) + \alpha (G - Q(s, a))

α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} pour l'estimation de la moyenne. Les seules valeurs à stocker sont les estimations actuelles des valeurs d'action Q(s,a)Q(s, a) et le nombre de fois que la paire état-action (s,a)(s, a) a été visitée N(s,a)N(s, a).

Pseudocode

Contrôle Monte Carlo Hors-Politique

Pour la méthode hors-politique avec l'échantillonnage d'importance ordinaire, tout est identique à la méthode sur-politique.

Une situation plus intéressante se présente avec l'échantillonnage d'importance pondéré. L'équation reste la même :

Q(s,a)Q(s,a)+α(GQ(s,a))Q(s, a) \gets Q(s, a) + \alpha (G - Q(s, a))

mais α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} ne peut pas être utilisé car :

  1. Chaque retour est pondéré par ρ\rho ;
  2. La somme finale est divisée non pas par N(s,a)N(s, a), mais par ρ(s,a)\sum \rho(s, a).

La valeur de α\alpha qui peut réellement être utilisée dans ce cas est égale à WC(s,a)\displaystyle \frac{W}{C(s,a)} où :

  • WW est le ρ\rho pour la trajectoire courante ;
  • C(s,a)C(s, a) est égal à ρ(s,a)\sum \rho(s, a).

Et chaque fois que la paire état-action (s,a)(s, a) apparaît, le ρ\rho de la trajectoire courante est ajouté à C(s,a)C(s, a) :

C(s,a)C(s,a)+WC(s, a) \gets C(s, a) + W

Pseudocode

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 4. Chapitre 7

Demandez à l'IA

expand

Demandez à l'IA

ChatGPT

Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion

course content

Contenu du cours

Introduction à l'Apprentissage par Renforcement

Introduction à l'Apprentissage par Renforcement

1. Théorie Fondamentale de l'Apprentissage par Renforcement
2. Problème du Bandit Manchot
3. Programmation Dynamique
4. Méthodes de Monte Carlo
5. Apprentissage par Différence Temporelle

book
Implémentations Incrémentales

Stocker chaque retour pour chaque paire état-action peut rapidement épuiser la mémoire et augmenter considérablement le temps de calcul — en particulier dans des environnements de grande taille. Cette limitation affecte aussi bien les algorithmes de contrôle Monte Carlo on-policy qu'off-policy. Pour y remédier, nous adoptons des stratégies de calcul incrémentiel, similaires à celles utilisées dans les algorithmes multi-armed bandit. Ces méthodes permettent de mettre à jour les estimations de valeur à la volée, sans conserver l'historique complet des retours.

Contrôle Monte Carlo On-Policy

Pour la méthode on-policy, la stratégie de mise à jour ressemble à celle utilisée dans les algorithmes MAB :

Q(s,a)Q(s,a)+α(GQ(s,a))Q(s, a) \gets Q(s, a) + \alpha (G - Q(s, a))

α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} pour l'estimation de la moyenne. Les seules valeurs à stocker sont les estimations actuelles des valeurs d'action Q(s,a)Q(s, a) et le nombre de fois que la paire état-action (s,a)(s, a) a été visitée N(s,a)N(s, a).

Pseudocode

Contrôle Monte Carlo Hors-Politique

Pour la méthode hors-politique avec l'échantillonnage d'importance ordinaire, tout est identique à la méthode sur-politique.

Une situation plus intéressante se présente avec l'échantillonnage d'importance pondéré. L'équation reste la même :

Q(s,a)Q(s,a)+α(GQ(s,a))Q(s, a) \gets Q(s, a) + \alpha (G - Q(s, a))

mais α=1N(s,a)\displaystyle \alpha = \frac{1}{N(s, a)} ne peut pas être utilisé car :

  1. Chaque retour est pondéré par ρ\rho ;
  2. La somme finale est divisée non pas par N(s,a)N(s, a), mais par ρ(s,a)\sum \rho(s, a).

La valeur de α\alpha qui peut réellement être utilisée dans ce cas est égale à WC(s,a)\displaystyle \frac{W}{C(s,a)} où :

  • WW est le ρ\rho pour la trajectoire courante ;
  • C(s,a)C(s, a) est égal à ρ(s,a)\sum \rho(s, a).

Et chaque fois que la paire état-action (s,a)(s, a) apparaît, le ρ\rho de la trajectoire courante est ajouté à C(s,a)C(s, a) :

C(s,a)C(s,a)+WC(s, a) \gets C(s, a) + W

Pseudocode

Tout était clair ?

Comment pouvons-nous l'améliorer ?

Merci pour vos commentaires !

Section 4. Chapitre 7
some-alt