[PYTHON] Apprentissage par renforcement 2 Processus de décision de Markov, équation de Belman

Aidemy　2020/11/15

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 deuxième article sur le renforcement de l'apprentissage. 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 ・ Composantes de l'apprentissage amélioré ・ À propos du processus de décision Markov ・ Valeur, profit, condition ・ À propos de la meilleure politique ・ À propos de l'équation de Bellman

Composantes de l'apprentissage par renforcement

Problème de bande de bras N et étapes suivantes

-Le problème des bandes N-bras traité au chapitre 1 est un problème plus simple que le problème général en ce qu'il est __ "récompense immédiate" __ points et __ "l'état ne change pas en fonction de l'action de l'agent" . Rencontré. - State__ représente __ quel est l'état actuel de environment. C'est facile à comprendre lorsqu'on considère un jeu de société. Lorsque le joueur qui est un agent utilise un mouvement de l'adversaire dans l'environnement du shogi, le plateau a changé par rapport à son tour précédent, donc l'action à effectuer ensuite change également. A ce moment, on peut dire que l'état de __ "board" __ a changé. -De plus, comme je l'ai évoqué dans le chapitre 1, le but initial du renforcement de l'apprentissage est de maximiser __ les récompenses retardées telles que "gagner le jeu" au lieu de récompenses immédiates. ・ Cette fois, nous effectuerons un apprentissage par renforcement qui incorpore ces concepts de __ "état" et "temps" __.

À propos du modèle d'apprentissage par renforcement

・ L'apprentissage intensifié est __ "(1) L'agent reçoit l'état $ s_ {t} $ et provoque l'action $ a_ {t} $ pour agir sur l'environnement." "Transition" "③ L'environnement donne à l'agent $ r_ {t + 1} $" "④ L'agent décide de l'action suivante $ a_ {t + 1} $ en fonction du résultat de ②③" __ Il continuera avec. -__ "T" __ est __ "pas de temps" __ indiquant combien de fois l'opération est effectuée. C'est l'unité de temps de base pour l'apprentissage intensif.

Formulation d'états, d'actions et de récompenses

-Ce qui suit est un ensemble de states qui peuvent être prises par l'environnement. S={s_{0},s_{1},s_{2},...} -De même, le ensemble d'actions __ qu'un agent peut entreprendre est exprimé comme suit. A(s)={a_{0},a_{1},a_{2},...} - Récompense "$ R_ {t + 1} $" au pas de temps "t + 1" est exprimé comme suit. R_{t+1}=r(S_{t},A_{t},S_{t+1})

・ Lorsque la récompense est calculée par la formule ci-dessus, $ R_ {t + 1} $ est appelée __fonction de récompense __. Comme vous pouvez le voir à partir de cette fonction de récompense, l'état __future est déterminé de manière probabiliste uniquement par l'état / comportement actuel (t, t + 1), et n'a rien à voir avec le comportement passé __. __ Appelée "propriété Markov" __.

Processus décisionnel de Markov

Quel est le processus de décision Markov?

-Comme vu dans la section précédente, __ l'état futur n'est déterminé que par l'état actuel et les actions __ sont appelées __ "propriété Markov" __. Et le processus de renforcement de l'apprentissage qui satisfait cela s'appelle __ "Processus de détermination de Markov (MDP)" __. -Le processus de Markov se compose d'un ensemble d'états __ "espace d'état $ S $" _, d'un ensemble d'actions __ "espace d'action $ A (s) $" , et d'une variable de probabilité __ "distribution d'état initial" qui représente l'état au début. $ P {0} $ ", lorsque l'action $ a $ est effectuée dans l'état $ s $, le taux de transition de la probabilité de devenir l'état $ s '$ est " probabilité de transition d'état $ P (s' | s, a ) $ ”, “ Fonction de récompense $ r (s, a, s ') $ ” a cinq éléments.

-La figure ci-dessous montre l'environnement __ "Environnement 1" __ utilisé cette fois. On montre qu'en partant de StateA et en prenant une actionX, il passe à StateB avec une probabilité de "0,7" et revient à StateA avec une probabilité de "0,3". Enfin, dans StateB, si vous tirez "0.8" d'actionX, vous atteindrez l'objectif (Fin).

・ Dans chaque cas, les 5 éléments ci-dessus__[s,s',a,p(s'|a,s),r(s,a,s')]Ce qui est exprimé comme"Diagramme de transition d'état"__C'est.(Quel état est maintenant, s'À quel état aller ensuite, a est actionX ou Y, p(s'|a,s)Est sa probabilité, r(s,a,s')Est la récompense)

-Le code suivant est un résumé de tous les diagrammes de transition d'état de cet environnement 1 sous forme de tableau. Lorsque vous créez un tableau, remplacez-le par des valeurs numériques telles que StateA = 0, StateB = 1, End = 2.

Présentation du concept d'état-temps et de comportement

-Comme le concept de time n'a pas encore été introduit dans les cinq variables de la section précédente, qui sont les composantes du processus de détermination de Markov, nous allons introduire ces concepts de temps et les formuler. -Pour l'espace d'états S, définissez "$ S {t} " qui incorpore le concept de temps t et " A {t} " qui introduit le concept de temps dans les actions. -Le tableau utilisé dans la définition est le __ "diagramme de transition d'état" __ dans la section précédente. Puisque la __0ème colonne __ de ce tableau est "état", c'est-à-dire "état actuel (au moment de t)", cela devient __ " S_ {t} " __, et la ___2ème colonne __ est "action". En d'autres termes, il s'agit d'une "action au temps t", donc c'est __ " A_ {t} $" . -Ce qui suit est une fonction qui renvoie $ A {t} $ qui résume les actions __ que l'agent peut entreprendre dans cet état lorsque $ S {t} $ est passé.

-__ "actions ()" __ Le __ "état" __ passé à la fonction est l'état "$ S_ {t} ", et le __ "state_transition" __ référencé par A est la transition __state. Figure __. Puisque cette 0ème colonne est " S_ {t} $", décrivez que cette partie se réfère à celle dans le même état que l'état passé, et __ "A [:, 2]" __ dans la 2ème colonne Renvoie une liste d'actions possibles $ A_ {t} $ à ce moment en se référant à. À ce stade, la valeur de retour est une action possible, elle ne doit donc pas être dupliquée, c'est-à-dire qu'elle doit être un élément __unique __. Pour ce faire, utilisez __ "np.unique ()" __.

-Pour la partie exécution, l'état actuel est __ "state = [1]" __ indiquant qu'il est dans l'état B. Si vous regardez la partie s (état actuel) de state_transition, c'est-à-dire la deuxième colonne de la ligne où la 0ème colonne est [1], 0 ou 1 est stockée, elles sont donc renvoyées comme résultat de la fonction.

Présentation du concept de temps-autre

・ Ici, la distribution d'état initiale, la probabilité de transition d'état et la fonction de récompense sont redéfinies en incorporant le concept de temps. -La distribution de l'état initial est simple et vous pouvez définir l'état $ S_ {0} $ lorsque t = 0. -La probabilité de transition d'état est déterminée uniquement par le processus de détermination Markov , et l'état $ S {t + 1} $ au temps $ t + 1 $ n'est déterminé que par $ S {t} $ et $ A {t} $. , $ P (s '| s {t}, a_ {t}) $. -Pour Reward __ $ R {t + 1} $ lors du passage à l'état $ S {t + 1} $, $ R_ {t + 1} = r (s_ {t}, a_ {t}, Il peut être représenté par s_ {t + 1}) $. Le code suivant définit cette fonction de récompense.

-Pour cette fonction __ "R" , passez les $ s {t}, a {t}, s_ {t + 1} $ mentionnés ci-dessus comme arguments. Par principe, lorsque __ est déjà au terminal, 0 est renvoyé car il n'y a pas de récompense. -Cette fois également, la récompense est retournée en faisant référence à "state_transition", mais comme reward est dans la __4ème colonne de ce tableau, l'état (ligne) qui remplit les conditions est extrait et que Vous pouvez renvoyer la 4e colonne. -La condition cette fois-ci est de trouver le correspondant "état, after_state, action" passé comme argument à partir des 0ème, 1ère et 2ème colonnes de state_transition.

-Comme pour la partie exécution, l'état est [1], after_state est [2] et l'action est [0], donc __ "J'étais dans l'état B et je suis arrivé à la fin en exécutant l'action X" __ Transition d'état Vous pouvez vous référer à. Dans l'état_transition cette fois, il est [1, 2, 0, 0.8, 100] dans la 4ème ligne, donc la récompense dans la 4ème colonne est sortie.

épisode

-Le temps qu'il faut du début à la fin d'une tâche s'appelle __ "épisode" __. En répétant plusieurs fois le cycle «comportement → changement d'état», le pas de temps progresse et un épisode est composé. ・ Dans le modèle d'apprentissage par renforcement, pour cet épisode unique __ "Initialisez l'environnement, laissez l'agent agir et optimisez le modèle de comportement en fonction de la récompense reçue" __ Faites-le plusieurs fois __ Ce faisant, nous procéderons à l'apprentissage. ・ Il est très facile à comprendre comme exemple de jeu de cartes au tour. Le plateau change en fonction des actions du joueur à chaque tour, et la tâche se termine sous la forme de "gagner ou perdre". Avec ceci en un seul épisode, en jouant les uns contre les autres plusieurs fois, vous apprendrez progressivement le meilleur coup.

-Ce qui suit est la fonction __ "T ()" __ qui définit l'épisode. Cette fonction __ "transmet l'état et l'action actuels, extrait le correspondant de state_transition et renvoie la probabilité de transition d'état et l'état après la transition" __.

-Pour la partie définition de T, lorsque __ est déjà aux extrémités (terminaux), __ [(0, terminaux)] __ est renvoyé car l'état ne change pas. -Pour X, les lignes qui correspondent aux arguments passés sont extraites comme dans la section précédente. Stockez __ "3e colonne (probabilité de transition d'état)" __ et __ "1ère colonne (état après transition)" __ dans cette ligne dans A, et __ "tuple (tuple) pour tous les cas possibles. A [i ,:]) ”__ pour tuple et retourner.

Valeur / profit / état

Récompenses et gains

・ Jusqu'à présent, nous avons modélisé et défini l'apprentissage par renforcement. À partir de là, nous considérerons __ "Quelle est la base pour trouver la politique optimale?" __. ・ Lorsque vous envisagez d'utiliser __reward __ comme index, cela n'est déterminé que par l'action immédiatement avant __, donc __ "Même si l'action est de peu de valeur à ce moment-là, elle sera d'une grande valeur après cela. Je néglige __. -La solution à cela est __ "profit" _. Puisque le revenu est calculé par __ le total des récompenses obtenues au cours d'une certaine période , les récompenses après __ peuvent être prises en considération . ・ Si la récompense obtenue par l'action $ a {t} $ au temps t est __ "$ R {t} " __, alors la somme des récompenses dans une certaine période est le profit __ " G {t}" $ " Peut être calculé par la formule suivante. $ G_{t} =R_{t+1} + \gamma R_{t+2}+ \gamma^2 R_{t+3}+....= \displaystyle\sum_{\tau=0}^{\infty} \gamma^{\tau} R_{t+1+\tau} $

• $ \ Gamma $ est appelé __ "taux d'actualisation" __ et prend la valeur de __ (0 à 1) __. Cela représente __ "combien la récompense que vous recevrez dans le futur est la valeur actuelle" __. Plus elle est proche de 0, moins vous trouverez la valeur future, et plus elle est proche de 1, plus vous aurez de poids dans la valeur future. Sera.

-Bien qu'il existe plusieurs méthodes pour calculer la récompense totale, la __ "somme des récompenses à rabais" __ est généralement utilisée. Ceci est calculé en calculant la moyenne __ des bénéfices entre __temps t et un certain temps T, et en prenant la limite de __T __. -La somme des récompenses de réduction peut être définie par deux fonctions comme suit.

-Pour __ "take_single_action ()" __, il s'agit de la fonction __ "déterminer l'état suivant en fonction de la probabilité de transition" _. En tant que code, le premier __ "random.uniform (0,1)" __ génère un nombre aléatoire de 0 à 1. De plus, __ probabilité cumulative «probabilité cumulative» __ est définie. -Dans l'instruction for, la probabilité possible __ "probabilité" __ et l'état suivant __ "next_state" __ sont extraits de l'état passé et de l'action pour chaque épisode "T", et la probabilité cumulative "cumlative_probability" Ajoutez "probabilité" pour chaque épisode à, et lorsque cela devient plus grand que "x", terminez l'instruction for et renvoyez "next_state" à ce point.

-Pour une autre fonction __ "Calculate_value ()" __, c'est la fonction qui calcule __ "rabais récompense somme" _. Premièrement, «état» et «action» et discount récompense somme «sumg» __ sont définis. -Dans la déclaration for, répétez __ pour le nombre de __ épisodes. Cette fois, c'est deux fois. En cela, __ l'état suivant est défini par "take_single_action", et $ R {t + 1} $ est calculé en utilisant ceci et __ "state" "action" __ à ce moment-là, et ceci et Multipliez par $ \ gamma ^ i $ et accumulez __sumg. Ensuite, après avoir mis à jour "state", passez à l'épisode suivant et renvoyez la somme cumulative finale des remises "sumg".

・ Partie d'exécution

Fonction de valeur / fonction de valeur d'état

・ Dans la méthode comme la méthode de la section précédente, où __reward est utilisé comme norme d'évaluation de la politique, R est déterminé en fonction de la probabilité, donc plus les branches __state sont nombreuses, plus la formule de calcul devient compliquée. Il y a un inconvénient: cela finit par __. ・ En prenant la valeur attendue de __reward __, les inconvénients ci-dessus peuvent être éliminés. La valeur attendue de la récompense qui prend en compte toutes les actions après __ à partir d'un certain état est appelée «valeur» ou __ «valeur d'état» __. __ Plus la stratégie est bonne, plus la valeur de l'état est élevée. __. ・ En introduisant ce concept, «dans une certaine politique, __ quel état est le meilleur __ peut être comparé» et «lorsqu'un certain état est placé au point de départ, il est possible de comparer le bien et le mal de chaque __ politique __ Deux choses sont possibles.

À la recherche de la meilleure politique

Politique optimale

-En introduisant la fonction de valeur state __ dans la section précédente, il est devenu possible de comparer le bon et le mauvais de chaque measure . ・ Lors de la comparaison de deux mesures $ \ pi {1}, \ pi {2} $ -Dans tous les états de l'espace d'états S, la valeur de l'état $ V ^ {\ pi {1}} (s) $ est $ V ^ {\ pi {2}} (s) $ __ ou plus __ -Dans au moins un état s de l'espace d'états S, la valeur d'état $ V ^ {\ pi {1}} (s) $ est supérieure à $ V ^ {\ pi {2}} (s) $ __ __

Lorsque ces deux éléments tiennent, nous pouvons dire __ "$ \ pi_ {1} est une meilleure stratégie que \ pi_ {2} $" __. -A ce moment, la meilleure politique devrait exister parmi toutes les politiques, et cela s'appelle __optimal policy __ et est exprimé comme $ \ pi ^ * $.

Valeur de l'action

・ La fonction de valeur d'état est __ "valeur attendue de la récompense lorsqu'un certain état est démarré" , mais en réalité, " récompense lorsqu'un certain état est démarré et qu'une certaine action est entreprise" Dans de nombreux cas, il est préférable de considérer la valeur qui prend en compte action, telle que "valeur attendue". La valeur à ce moment est appelée __ "valeur d'action" __, et la fonction indiquant la valeur d'action sous une certaine mesure est appelée __ "fonction de valeur d'action" __. -La fonction de valeur d'action peut être considérée comme une fonction qui détermine __ la qualité de chaque "action". -Comme formule, utilisez la formule suivante de __ séries isométriques __. $a+ar + ar^2 + \cdots + ar^n = \large\frac{a(1 - r^n)}{1 - r}$

・ La fonction de valeur d'action peut être calculée avec "a" comme récompense et "r" comme gamma. Le code pour cela ressemble à ceci:

Fonction de valeur d'état optimale / fonction de valeur d'action optimale

-De la "fonction de valeur d'état" et de la "fonction de valeur d'action" que nous avons vues jusqu'à présent, chaque fonction en suivant la politique optimale est appelée __ "fonction de valeur d'état optimale" et "fonction de valeur d'action optimale" __ .. Ils sont respectivement exprimés en "$ V ^ \ * (s) " et " Q ^ \ * (s) $". ・ __ Une fois que la fonction de valeur d'état optimale et la fonction de valeur d'action optimale sont obtenues __, il est possible de savoir quelle action est l'action la plus rentable, donc toujours sélectionner l'action optimale __ "méthode gourmande" _ Sélectionnez simplement _.

Équation de Bellman

Valeur d'état optimale

-Pour __ pour trouver la fonction de valeur d'état optimale, __ pour trouver chaque fonction de valeur d'état et comparer __. La même chose s'applique à la fonction de valeur d'action, nous allons donc procéder ici à la fonction de valeur d'état. -Utilisez l'équation __Bellman __ pour trouver chaque fonction de valeur d'état. Ceci est basé sur l'idée de __ "établir une expression relationnelle de la fonction de valeur entre l'état s et l'état s qui peut se déplacer sous l'action" __. -L'équation de Belman peut être utilisée en faisant de chaque fonction une __ expression graduelle __ comme suit. V^{\pi}(s) =\displaystyle\sum_{\alpha \in A(s)}^{} \pi(a|s) \displaystyle\sum_{s' \in S}^{} P(s'|s,a)(r(s,a,s') + \gamma V^{\pi}(s'))

Q^{\pi}(s,a) =\displaystyle\sum_{s' \in S}^{} (P(s'|s,a) (r(s,a,s') + \displaystyle\sum_{a' \in A(s')}^{} \gamma \pi(a'|s') Q^{\pi}(s',a')))

-Ici, $ \ pi (a | s) $ représente __la probabilité que l'action soit sélectionnée __.

-Par exemple, dans "Environnement 1", lorsque __ "s = StateB", "$ \ gamma $ = 0.8" et "do only ActionX" __, la fonction de valeur est calculée par l'équation de Belman. $ V ^ \ pi (B) = 0,2 (-10 + \ gamma * V ^ \ pi (B)) +0,8 (100+ \ gamma * 0) $ comme l'équation pour $ V ^ \ pi (B) $ Résolvez-le. Autrement dit, pour le dire plus simplement, __ "(probabilité de provoquer cette action) x (récompense par action + $ \ gamma $ x état après mouvement)" __ est calculé pour tous les cas, et sa __ somme __ Vous pouvez résoudre l'équation en utilisant.

・ Environnement 1

Équation optimale de Bellman

-Bien entendu, l'équation de Belman peut être appliquée à la fonction d'état optimal et à la fonction de comportement optimale mentionnées ci-dessus. Par conséquent, __ l'équation de Belman __ lorsque la politique optimale est toujours prise est appelée __ "équation optimale de Bellman" . -Par exemple, lorsque vous comparez laquelle des règles "Toujours prendre une action X $ \ pi {1} $" et "Toujours prendre une action Y politique $ \ pi {2} $" est la meilleure politique dans l'environnement 1, __ profit (remise) Récompense) En utilisant la fonction __ "caluclate_value ()" __ qui calcule __, elle peut être exprimée comme suit.

-__ Q_optimum__ représente le profit maximum à ce moment, et Q_pi représente la politique à ce moment-là. Puisque Q_pi vaut [0 0], il vaut mieux prendre _measure $ \ pi {1} $ qui prend toujours ActionX.

Sommaire

-La récompense "R_ {t + 1}" au pas de temps "t + 1" est exprimée par $ r (S_ {t}, A_ {t}, S_ {t + 1}) $. À ce stade, le fait que l'état futur (t + 1) ne soit déterminé que par l'état et le comportement actuels (t) est appelé "propriété de Markov", et le processus d'apprentissage par renforcement qui satisfait cela est appelé processus de détermination de Markov. ・ Dans le processus de détermination de Markov, les composants sont représentés par un tableau tel que [s, s ', a, p (s' | a, s), r (s, a, s ')] dans le "diagramme de transition d'état". ". Lorsque le concept de temps est introduit, il est représenté par $ [S_ {t}, S_ {t + 1}, A_ {t}, S_ {0}, R_ {t + 1}] $. -Le temps écoulé entre le début et la fin d'une tâche est appelé un «épisode». Dans l'apprentissage par renforcement, cet épisode est appris à plusieurs reprises en «initialisant l'environnement et en l'optimisant en fonction des récompenses des actions de l'agent». ・ Dans l'apprentissage par renforcement réel, considérez les mesures optimales basées sur le «profit», y compris non seulement les récompenses immédiates mais également les récompenses tardives. Les revenus sont calculés par la "somme des récompenses de remise", qui est la somme de la récompense à chaque pas de temps multipliée par le "taux de remise $ \ gamma $". -De plus, lors de la recherche de la politique optimale, le montant du calcul augmentera si le profit est calculé tel quel, il est donc conseillé de calculer la "fonction de valeur d'état" et la "fonction de valeur d'action" qui sont les valeurs attendues de la récompense. L '«équation de Bellman» est utilisée pour les trouver. Si l'équation de Belman est utilisée pour la fonction de valeur d'état, elle est calculée en utilisant "probabilité de provoquer une action", "récompense" et "état après mouvement".

Cette fois, c'est fini. Merci d'avoir lu jusqu'ici.