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)+α(G−Q(s,a))où α=N(s,a)1 pour l'estimation de la moyenne. Les seules valeurs à stocker sont les estimations actuelles des valeurs d'action Q(s,a) et le nombre de fois que la paire état-action (s,a) a été visitée 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)+α(G−Q(s,a))mais α=N(s,a)1 ne peut pas être utilisé car :
- Chaque retour est pondéré par ρ ;
- La somme finale est divisée non pas par N(s,a), mais par ∑ρ(s,a).
La valeur de α qui peut réellement être utilisée dans ce cas est égale à C(s,a)W où :
- W est le ρ pour la trajectoire courante ;
- C(s,a) est égal à ∑ρ(s,a).
Et chaque fois que la paire état-action (s,a) apparaît, le ρ de la trajectoire courante est ajouté à C(s,a) :
C(s,a)←C(s,a)+WPseudocode
Merci pour vos commentaires !
Demandez à l'IA
Demandez à l'IA
Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion
Awesome!
Completion rate improved to 2.7
Implémentations Incrémentales
Glissez pour afficher le menu
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)+α(G−Q(s,a))où α=N(s,a)1 pour l'estimation de la moyenne. Les seules valeurs à stocker sont les estimations actuelles des valeurs d'action Q(s,a) et le nombre de fois que la paire état-action (s,a) a été visitée 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)+α(G−Q(s,a))mais α=N(s,a)1 ne peut pas être utilisé car :
- Chaque retour est pondéré par ρ ;
- La somme finale est divisée non pas par N(s,a), mais par ∑ρ(s,a).
La valeur de α qui peut réellement être utilisée dans ce cas est égale à C(s,a)W où :
- W est le ρ pour la trajectoire courante ;
- C(s,a) est égal à ∑ρ(s,a).
Et chaque fois que la paire état-action (s,a) apparaît, le ρ de la trajectoire courante est ajouté à C(s,a) :
C(s,a)←C(s,a)+WPseudocode
Merci pour vos commentaires !