[PYTHON] Apprentissage par renforcement 3 Méthode de planification dynamique / méthode TD

Aidemy　2020/11/16

introduction

Bonjour, c'est Yope! Je suis une école littéraire croustillante, mais j'étais intéressé par les possibilités de l'IA, alors je suis allé à l'école spécialisée en IA "Aidemy" pour étudier. Je voudrais partager les connaissances acquises ici avec vous, et je les ai résumées dans Qiita. Je suis très heureux que de nombreuses personnes aient lu l'article de synthèse précédent. Merci! Ceci est le troisième article sur l'apprentissage amélioré. Ravi de vous rencontrer.

• Cet article est un résumé de ce que vous avez appris dans "Aidemy" "dans vos propres mots". Il peut contenir des erreurs et des malentendus. Notez s'il vous plaît.

Quoi apprendre cette fois ・ À propos de la méthode de planification dynamique ・ À propos de la méthode TD

Méthode de planification dynamique

Qu'est-ce que la méthode de planification dynamique?

・ Dans le chapitre 2, j'ai expliqué que __ l'équation de Bellman __ est utilisée pour trouver la politique optimale, mais dans ce chapitre, __ je vais en fait faire cela __. -En supposant que le modèle de l'environnement est entièrement donné dans __ "Markov Decision Process (MDP)" __, la méthode pour trouver la politique optimale est appelée __ "Dynamic Planning (DP)" __.

Évaluation des politiques

-Calculer la fonction valeur $ V ^ \ pi (s) $ lorsque la méthode $ \ pi $ est prise s'appelle measure evaluation. La méthode d'exécution est la suivante. ・ Tout d'abord, définissez le seuil $ \ epsilon $ pour mettre à jour la politique à l'avance. Entrez ensuite la stratégie $ \ pi $, supposez que $ V (s) $ est 0 dans tous les états, et faites la différence dans tous les états plus petite que le __seuil lors de la mise à jour de , donc "$ \ Delta $ "est défini. ・ Une fois défini jusqu'à présent, "v" pour tous les états s=V(s)Comme__Avec l'équation de Belman「V(s)Est calculé. Afin de comparer le montant de la mise à jour, le "\delta""\max(\delta,|v-V(s)|)Et c'est "\epsilon"__S'il tombe en dessous__À ce stade, le calcul est terminé et "V(s)""V^\pi(s)La sortie suppose-t-elle une solution approximative de. -Le code ci-dessus est le suivant.

-Pour la fonction __ "policy_evaluation ()" __ qui évalue la politique, passez "policy pi, state states, threshold epsilon" comme argument. -__ Tout d'abord, définissez "$ \ delta = 0 " __. Ensuite, à partir de là, __ la méthode ci-dessus est exécutée pour tous les états s. Tout d'abord, affectez la fonction valeur V à la variable __ "v" __ avec __ "v = V.copy ()" __. Préparez également la variable __ "x" __ qui stocke les "V [s]" calculés dans le calcul suivant. -Pour __ "pour (p, s1) dans T (s, pi [s]):" __, __ "p" __ est obtenu dans l'épisode T __ "Probabilité de réaliser cette action ( \ pi ($ \ pi ($ \ pi) Dans un | s) $) "__, " s1 " est " État (after_state) de la destination de transition ". Utilisez-les pour calculer $ V (s) $ avec l'équation __Bellman __ (voir la formule du chapitre 2). Remplacez ceci par __ "x" __. ・ Calculez "$ \ delta $" en utilisant la formule ci-dessus en utilisant $ V (s) $ et $ v (s) , et s'il tombe en dessous du seuil " \ epsilon $", la valeur approximative de la fonction de valeur "V" rends le.

・ Partie d'exécution

-En regardant la partie exécution, il définit V, qui correspond à la partie "v" de __ "policy_evaluation ()" __, et pi à passer en argument. Suite à l'application de la fonction, la fonction de valeur __ de __StateA et la fonction de valeur __ de __StateB sont calculées respectivement.

Répétition de la politique

-Dans le "$ V ^ \ pi (s) " calculé par l'évaluation de la valeur dans la section précédente, si la mesure qui prend la méthode __greedy __ est " \ pi '", alors __ " V ^ \ pi ( s) $ <$ V ^ {\ pi '} (s) $ ”__, qui s'appelle amélioration de la valeur. -En répétant cette __ amélioration de la valeur et évaluation de la valeur __, la fonction de valeur __optimale peut être dérivée __. Cela s'appelle __ répétition de la politique __. -Le code de la fonction __ "policy_iteration ()" __ qui améliore la valeur est le suivant.

-Pour le code ci-dessus, initialisez d'abord la fonction value V et la stratégie pi. Après cela, pour V, l'évaluation de la mesure __ est effectuée avec la fonction "policy_evaluation ()" créée au chapitre 2. En même temps, définissez __ "policy_flag = True" __. -Pour chaque état s, calculer la politique pi avec l'équation allemande en utilisant le V mis à jour, et trier __action en fonction de cette __action. Ensuite, si la __measure n'est pas couverte, l'action est stockée dans __pi et la boucle se poursuit. Lorsque cela est fait, retournez la politique pi.

・ Partie d'exécution

-La fonction d'itération de politique __ "policy_iteration ()" __ renvoie la politique pi, donc ce résultat d'exécution représente la politique consistant à "prendre ActionX dans l'état A et entreprendre l'action X dans l'état B".

Répétition de valeur

・ Dans l'itération de politique de la section précédente, afin de calculer __policy pi, il est nécessaire de recalculer la fonction de valeur pour tous les états __ plusieurs fois __, et la quantité de calcul augmente à mesure que le nombre d'états augmente. Cela augmentera. La solution à ce problème est une technique appelée __ "itération de valeur" __. -Dans l'itération de valeur, la fonction de valeur est directement obtenue et mise à jour pour chaque état s afin de calculer la __value v, ainsi la fonction __value ne peut être calculée qu'une seule fois __. -Ce qui suit est le code de la fonction d'itération de valeur __ "value_iteration ()" __.

-Pour cette fonction, tout d'abord, la valeur __state V est initialisée comme avant __. Contrairement à l'itération de stratégie, __policy pi n'est pas considéré __, il n'est donc pas nécessaire d'initialiser __pi __. Ensuite, pour chaque action, __ évaluation de la mesure __ est effectuée et la __ valeur maximale de $ V (s) $ calculée est mise à jour __. -Enfin, calculez l'action qui obtient le plus de récompense de ce __ $ V (s) $ __ et renvoyez-la comme politique "pi". L'action la plus gratifiante à ce moment peut être calculée de la même manière que lorsque la politique est répétée dans la section précédente.

・ Partie d'exécution

Méthode TD

Quelle est la méthode TD?

-La méthode ci-dessus est la __ méthode de planification dynamique__, et la probabilité de transition d'état P doit être connue à l'avance . Au contraire, lorsque la probabilité de transition d'état n'est pas connue, il est nécessaire de l'estimer à partir des récompenses réellement collectées, comme appris au chapitre 1. -Il existe une __ "méthode TD" __ comme méthode d'estimation. Abréviation de TimeDifferance, qui est effectuée en mettant à jour la valeur estimée suivante à l'aide de __ valeur estimée actuelle sans voir le résultat final. -Il existe des méthodes telles que __ "Sarsa" et "Q-learning" __ dans la méthode TD.

・ Ensuite, utilisez le __ "Environnement 2" __ suivant.

-Le point de départ est la cellule "début" de la figure, le point final est la cellule "+1" ou "-1", et la cellule noire n'est pas transposable et peut se déplacer vers le haut, le bas, la gauche et la droite de la cellule adjacente. De plus, avec une probabilité de __80% __, il est possible d'effectuer une transition telle que sélectionnée, mais avec ___% __, elle effectuera une transition de 90 degrés dans le sens des aiguilles d'une montre dans la direction sélectionnée, et avec les ___% __ restants, elle passera dans le sens inverse des aiguilles d'une montre. Faire. Quant à la récompense, on suppose que la cellule terminale est __le score __ et les autres cellules sont __ "-0,04" __. -Le code suivant est une fonction qui affiche la position lorsque vous essayez de déplacer __ "deux vers le haut, trois vers la droite" __ à partir du point de départ.

・ Parce que nous allons utiliser un nouvel environnement, définissez-le d'abord. Puisque la fonction __ "T ()" __ qui définit l'épisode est utilisée dans "take_single_action ()", elle est définie de sorte que la 0ème colonne renvoie un tableau de probabilily et la 1ère colonne renvoie un tableau de next_state. De plus, pour changer l'état de next_state, créez __ "go ()" __ qui définit __ destination __ à partir de l'état et de la direction. -La fonction __ "take_single_action ()" __, qui détermine l'état suivant en fonction de la probabilité de transition, est également utilisée ici. L '"état suivant" est mis à jour jusqu'à ce que la "probabilité de transition" définie dans le "T ()" ci-dessus dépasse x, et la récompense à la fin de la mise à jour est établie. -Enfin, créez une fonction __ "move ()" __ qui se déplace réellement "2 fois vers le haut de l'état actuel et 3 fois vers la droite". En tant qu'actions, la __0ème colonne définit le mouvement vers le haut et vers le bas, la 1ère colonne définit le mouvement vers la gauche et vers la droite __, se déplace avec take_single_action deux fois pour la 0ème colonne et se déplace 3 fois pour la 1ère colonne pour mettre à jour l'état. ..

・ Partie d'exécution

・ Chaque cellule est définie pour l'environnement. L'emplacement initial et le point final sont également définis, et l'état après le mouvement peut être trouvé en utilisant move ().

Sarsa ・ Sarsa est l'une des méthodes TD, et résout l'équation __Bellman __ par essais et erreurs. Dans l'itération de valeur, etc., $ V (s) $ a été utilisé, mais ici __ la fonction de valeur d'action $ Q (s, a) $ est utilisée __. Cette fonction Q est représentée par un tableau de __ [tous les états x toutes les actions] __. -En ce qui concerne "tous les états" à ce moment, dans l'environnement 2, il y a 11 états possibles et 4 "toutes les actions" en haut, en bas, à gauche et à droite. Par conséquent, je veux faire de la fonction Q un tableau 11x4, mais comme __state est représenté par les coordonnées __, cela ne peut pas être bien exprimé. Par conséquent, la partie d'état est associée à __ "coordonnée x x 10 + coordonnée y x 1" __.

-Le code spécifique est le suivant. (La partie qui chevauche la section précédente est omise)

-__ "Get_action ()" __ est une fonction qui détermine l'action en fonction de la valeur maximale de la fonction Q (q_table) __ définie ultérieurement. Le __ "t_state" __ passé à ce moment est le __ "état avec coordonnées converties" __ décrit ci-dessus. - "Take_single_action ()" __ a le même objectif que le précédent, mais lorsque la récompense n'est pas définie comme valeur renvoyée, c'est-à-dire lorsque __ la destination de l'action ne peut pas se déplacer en raison d'un mur ou d'un obstacle __ , Renvoie l'état «état» et récompense «-0,04» dans le sens de l'arrêt sur place, et renvoie «état suivant» et sa récompense dans le carré où la récompense est définie. -__ "update_qtable ()" __ est une fonction qui calcule et met à jour la fonction de valeur action Q. La formule utilisée au moment de cette mise à jour est: $Q(s,a) += \alpha[r + \gamma Q(s',a') - Q(s,a)]$

・ Ce $ \ alpha $ correspond au learning rate et doit être défini à l'avance. Cette fois, définissez avec __ "0,4" __. Le taux d'escompte $ \ gamma $ est de __ "0,8" __. De plus, l'état passé à ce moment est également appelé "état dans lequel les coordonnées sont converties". Le calcul lui-même peut être effectué selon la formule. -Enfin, créez une fonction __ "trans_state ()" __ qui change l'état "état" en "état avec coordonnées converties".

-Partie d'exécution

-Lors de l'exécution de Sarsa, initialisez d'abord la fonction de valeur action Q. Cette fois, le nombre d'épisodes est de 500, le pas de temps est jusqu'à 1000 fois, et __ "la récompense moyenne est de 0,7 ou plus pendant 5 fois consécutives" __ est défini comme condition de fin de l'épisode, alors préparez un tableau pour gérer cela. L'environnement est le même que dans la section précédente. -Ensuite, pour chacun des 500 épisodes, répétez tout après __ (jusqu'à ce que la condition de fin soit remplie) __. ・ Commencez par initialiser __state __. Sur cette base, le "t_state" et l'action "action" à passer à la fonction Q sont calculés. Utilisez respectivement les fonctions "trans_state ()" et "get_action ()". ・ Ensuite, pour chaque pas de temps de l'épisode __ "take_single_action ()" __, obtenez l'état suivant s'et récompense r lorsque l'action a est effectuée, et accumule __ récompenses __ J'irai. Aussi, pour l'état s ', le "t_next_state" et l'action "next_action" à passer à la fonction Q sont calculés. -Passez-les à __ "update_qtable ()" __ pour mettre à jour la fonction de valeur __action __. Mettez également à jour l'état et l'action pour passer à l'étape suivante. ・ Lorsque vous atteignez enfin le point final, cet épisode se termine et vous passez à l'épisode suivant. Avant de déménager, mettez à jour __ "total_reward_vec" pour la récompense qui est la condition de fin de l'épisode et affichez-la. De même, il affiche le numéro de l'épisode qui s'est terminé et le nombre d'étapes qu'il a prises. ・ Si la __ valeur minimale __ de ce "total_reward_vec" dépasse 0,7, la répétition de l'épisode prendra fin.

-Résultat de l'exécution (partie seulement)

-En regardant les résultats de l'exécution, les épisodes avec une récompense de «0,2» ont été exclus des 5 derniers épisodes, et toutes les récompenses se sont terminées dans l'épisode 21 + 1 supérieur à 0,7.

Implémentation de la méthode ε-gourmande dans Sarsa

-Dans la méthode de la section précédente, seule la valeur maximale de la fonction Q a été sélectionnée, mais avec cela, il y a un risque de manquer une meilleure méthode que __. Pour éviter cela, nous rechercherons de nouvelles méthodes en utilisant la méthode __ε-greedy __. ・ Bien que la méthode ε-gourmande ait été utilisée au chapitre 1, elle est utilisée avec un léger changement. Cette fois, nous utilisons la méthode __ "Augmentez ε pour augmenter le taux de recherche pendant que l'épisode est précoce, et diminuez la valeur de ε pour affiner la recherche au fur et à mesure de la progression de l'épisode." Ce qui suit est utilisé comme formule. $\epsilon = 0.5 * (1 / ( episode + 1)) $

-Le code spécifique est le suivant, seule la partie "get_action ()" est différente.

-Pour la fonction ci-dessus, calculez d'abord "epsilon" avec la formule ci-dessus. Si cet epsilon est inférieur ou égal au nombre aléatoire uniforme "np.random.uniform (0,1)", __ déterminer l'action suivante en fonction de la valeur maximale de la fonction Q comme dans la section précédente __, sinon. __ Décidez au hasard de l'action suivante __.

・ Partie d'exécution

-Bien que la partie exécution soit presque la même que la section précédente, __ "action" __ définie au début est déterminée en utilisant la valeur maximale de la fonction Q sans appliquer get_action () impliquant des nombres aléatoires. .. Cette fonction est utilisée pour next_action.

Apprentissage Q

-Il existe une méthode TD appelée __ "Q learning" __ qui est différente de Sarsa. C'est fondamentalement la même chose que Sarsa, mais la différence est que dans le traitement de chaque pas de temps, c'est la fonction __Q qui met à jour la fonction Q après avoir déterminé l'action suivante __. L'apprentissage Q est __ qui décide de la prochaine action après la mise à jour. -Par conséquent, ne passez pas __ "next_action" ___ à la fonction __ "update_Qtable ()" __, calculez plutôt la valeur maximale "next_max_q" __ de la fonction __Q dans next_state et utilisez-la. Mettez à jour la fonction Q. A part cela, c'est exactement la même chose que Sarsa.

Sommaire

-Lorsque le modèle de l'environnement est complètement donné dans le processus de détermination de Markov, la méthode de recherche de la politique optimale en utilisant l'équation de Belman au chapitre 2 est appelée "méthode de planification dynamique (DP)". -Calculer la fonction de valeur $ V ^ \ pi (s) $ quand une certaine méthode $ \ pi $ est prise est appelé évaluation de politique. De plus, on sait que la fonction de valeur devient plus grande lorsque la méthode gourmande est adoptée, et c'est ce qu'on appelle l'amélioration de la valeur. La méthode optimale peut être trouvée en répétant l'évaluation et l'amélioration, et c'est ce qu'on appelle la répétition des politiques. -En tant qu'application de l'itération de politique, la méthode de mise à jour de la fonction de valeur pour calculer la valeur au lieu de la politique est appelée itération de valeur. En conséquence, la quantité de calcul de la fonction de valeur peut être considérablement réduite. -Puisque l'itération de politique et l'itération de valeur sont des méthodes de planification dynamique et ne peuvent être utilisées que pour les modèles ayant un taux de transition d'état, la méthode TD est utilisée pour les modèles pour lesquels cela n'est pas donné. Les méthodes TD comprennent l'apprentissage Sarsa et Q. ・ Pour l'apprentissage Sarsa et Q, considérez la politique optimale en calculant la fonction de valeur d'action Q à l'aide de l'équation de Belman.

Cette fois, c'est fini. Merci d'avoir lu jusqu'à la fin.