[PYTHON] Verstärkungslernen 3 Dynamische Planungsmethode / TD-Methode

Aidemy　2020/11/16

Einführung

Hallo, es ist ja! Obwohl es ein knuspriges literarisches System ist, interessierte ich mich für die Möglichkeiten der KI, also ging ich zur KI-Fachschule "Aidemy", um zu studieren. Ich möchte das hier gewonnene Wissen mit Ihnen teilen und habe es in Qiita zusammengefasst. Ich freue mich sehr, dass viele Menschen den vorherigen zusammenfassenden Artikel gelesen haben. Vielen Dank! Dies ist der dritte Beitrag zum verbesserten Lernen. Freut mich, dich kennenzulernen.

• Dieser Artikel ist eine Zusammenfassung dessen, was Sie in "Aidemy" "in Ihren eigenen Worten" gelernt haben. Es kann Fehler und Missverständnisse enthalten. Bitte beachten Sie.

Was diesmal zu lernen ・ Informationen zur dynamischen Planungsmethode ・ Informationen zur TD-Methode

Dynamische Planungsmethode

Was ist eine dynamische Planungsmethode?

・ In Kapitel 2 habe ich erklärt, dass __Bellman-Gleichung __ verwendet wird, um die optimale Richtlinie zu finden, aber in diesem Kapitel __ werde ich dies tatsächlich tun __.

• Unter der Annahme, dass das Modell der Umgebung vollständig in __ "Markov Decision Process (MDP)" __ angegeben ist, heißt die Methode zum Finden der optimalen Richtlinie __ "Dynamic Planning (DP)" __.

Politische Bewertung

-Die Berechnung der Wertfunktion $ V ^ \ pi (s) $ bei Verwendung der Methode $ \ pi $ wird als Messungsbewertung bezeichnet. Die Ausführungsmethode ist wie folgt. ・ Legen Sie zunächst den Schwellenwert $ \ epsilon $ fest, um die Richtlinie im Voraus zu aktualisieren. Geben Sie dann die Strategie $ \ pi $ ein, nehmen Sie an, dass $ V (s) $ in allen Zuständen 0 ist, und machen Sie den Unterschied in allen Zuständen kleiner als der Schwellenwert , wenn Sie __ aktualisieren, also "$ \ Delta $ "ist definiert. ・ Einmal definiert, "v" für alle Zustände s=V(s)Wie__Mit der Belman-Gleichung「V(s)Ist berechnet. Um den Aktualisierungsbetrag zu vergleichen, wird der vordefinierte "\delta""\max(\delta,|v-V(s)|)Und das ist "\epsilon""__Wenn es darunter fällt__Zu diesem Zeitpunkt ist die Berechnung abgeschlossen und "V(s)""V^\pi(s)Wird die Ausgabe unter der Annahme einer ungefähren Lösung von. -Der Code für die oben genannten ist wie folgt.

-Für die Funktion __ "policy_evaluation ()" , die die Richtlinie auswertet, übergeben Sie "Richtlinie pi, Statuszustände, Schwellenwert epsilon" als Argument. - Definieren Sie zuerst "$ \ delta = 0 " __. Dann wird von hier aus __ die obige Methode für alle Zustände s ausgeführt. Weisen Sie zunächst der Variablen __ "v" __ mit __ "v = V.copy ()" __ die Wertfunktion V zu. Bereiten Sie auch die Variable __ "x" __ vor, in der die in der nächsten Berechnung berechneten "V [s]" gespeichert sind. -Für __ "für (p, s1) in T (s, pi [s]):" __, __ "p" __ wird in Episode T erhalten __ "Wahrscheinlichkeit, diese Aktion auszuführen ( \ pi ($ \ pi ($ \ pi)) a | s) $) "__, " s1 " ist " Status (after_state) des Übergangsziels ". Verwenden Sie diese, um $ V (s) $ mit der __Belman-Gleichung __ zu berechnen (siehe Formel in Kapitel 2). Ersetzen Sie dies durch __ "x" __. ・ Berechnen Sie "$ \ delta $" mit der obigen Formel unter Verwendung von $ V (s) $ und $ v (s) . Wenn der Schwellenwert " \ epsilon $" unterschritten wird, wird der ungefähre Wert der Wertefunktion "V" verwendet. Gib es zurück.

・ Ausführungsteil

• Mit Blick auf den Ausführungsteil wird V definiert, das dem Teil "v" von __ "policy_evaluation ()" __ entspricht, und pi, das als Argument übergeben werden soll. Als Ergebnis der Anwendung der Funktion werden die Wertfunktion __ von __StateA und die Wertfunktion __ von __StateB berechnet.

Richtlinienwiederholung

• Wenn in den "$ V ^ \ pi (s) ", die durch die Wertevaluierung im vorherigen Abschnitt berechnet wurden, das Maß für die __greedy-Methode __ " \ pi '" ist, dann __ " V ^ \ pi ( s) $ <$ V ^ {\ pi '} (s) $ ”__, was als Wertverbesserung bezeichnet wird.
• Durch Wiederholen dieser __Wertverbesserung und Wertbewertung __ kann die __optimale Wertfunktion __ abgeleitet werden. Dies nennt man __policy repetition __. -Der Code der Funktion __ "policy_iteration ()" __, die den Wert verbessert, lautet wie folgt.

-Für den obigen Code initialisieren Sie zuerst die Wertfunktion V und die Richtlinie pi. Anschließend wird für V die Kennzahlbewertung mit der in Kapitel 2 erstellten Funktion "policy_evaluation ()" durchgeführt. Setzen Sie gleichzeitig __ "policy_flag = True" __.

• Berechnen Sie für jeden Zustand s die Richtlinie pi mit der deutschen Gleichung unter Verwendung des aktualisierten V und sortieren Sie __action nach dieser __action. Wenn die __Maßnahme nicht abgedeckt ist, wird die Aktion in __pi gespeichert und die Schleife fortgesetzt. Wenn dies erledigt ist, geben Sie die Richtlinie pi zurück.

・ Ausführungsteil

-Die Richtlinieniterationsfunktion __ "policy_iteration ()" __ gibt die Richtlinie pi zurück, sodass dieses Ausführungsergebnis die Richtlinie "AktionX bei Status A und Aktion X bei Status B ausführen" darstellt.

Wertwiederholung

・ In der Richtlinieniteration des vorherigen Abschnitts ist es zur Berechnung von __policy pi erforderlich, die Wertefunktion für alle Zustände __ mehrfach zu berechnen __, und der Rechenaufwand nimmt mit zunehmender Anzahl von Zuständen zu. Es wird zunehmen. Die Lösung hierfür ist eine Technik namens __ "Wertiteration" __. -In der Wertiteration wird die Wertfunktion direkt für jeden Zustand s abgerufen und aktualisiert, um den __Wert v zu berechnen, sodass die __Wertfunktion nur einmal __ berechnet werden kann. -Das Folgende ist der Code der Wertiterationsfunktion __ "value_iteration ()" __.

-Für diese Funktion wird der erste __Statuswert V wie zuvor __ initialisiert. Im Gegensatz zur Richtlinieniteration wird __policy pi nicht als __ betrachtet, sodass __pi __ nicht initialisiert werden muss. Als nächstes wird für jede Aktion __Messungsbewertung __ durchgeführt und der __maximale Wert von $ V (s) $ berechnet __ aktualisiert.

• Berechnen Sie abschließend die Aktion, die die größte Belohnung für diese __ $ V (s) $ __ erhält, und geben Sie sie als Richtlinie "pi" zurück. Die derzeit lohnendste Aktion kann auf dieselbe Weise berechnet werden, wie wenn die Richtlinie im vorherigen Abschnitt wiederholt wird.

・ Ausführungsteil

TD-Methode

Was ist die TD-Methode?

-Die obige Methode ist dynamische Planungsmethode, und die Zustandsübergangswahrscheinlichkeit P muss im Voraus bekannt sein. Im Gegenteil, wenn die Zustandsübergangswahrscheinlichkeit nicht bekannt ist, muss dies aus den tatsächlich gesammelten Belohnungen geschätzt werden, wie in Kapitel 1 erfahren. -Es gibt eine __ "TD-Methode" __ als diese Schätzmethode. Abkürzung für TimeDifferance, die durchgeführt wird, indem der nächste geschätzte Wert unter Verwendung des aktuellen Schätzwerts aktualisiert wird, ohne das Endergebnis zu sehen. -Es gibt Methoden wie __ "Sarsa" und "Q-Learning" __ in der TD-Methode.

・ Verwenden Sie danach das folgende __ "Umgebung 2" __.

-Der Startpunkt ist die "Start" -Zelle in der Abbildung, der Endpunkt ist die "+1" - oder "-1" -Zelle, und die schwarze Zelle ist nicht übertragbar und kann sich von der benachbarten Zelle nach oben, unten, links und rechts bewegen. Darüber hinaus ist es mit einer Wahrscheinlichkeit von __80% __ möglich, einen Übergang wie ausgewählt durchzuführen. Mit ___% __ wird der Übergang in die ausgewählte Richtung um 90 Grad im Uhrzeigersinn und mit den verbleibenden ___% __ gegen den Uhrzeigersinn verschoben. Machen. Für die Belohnung wird angenommen, dass die Endzelle __die Punktzahl __ ist und die anderen Zellen __ "-0,04" __ sind. -Der folgende Code ist eine Funktion, die die Position ausgibt, wenn Sie versuchen, __ "zwei nach oben, drei nach rechts" __ vom Startpunkt zu bewegen.

・ Da wir eine neue Umgebung verwenden, definieren Sie diese zuerst. Da die Funktion __ "T ()" __, die die Episode definiert, in "take_single_action ()" verwendet wird, wird sie so definiert, dass die 0. Spalte das probabilily und die 1. Spalte das next_state Array zurückgibt. Um den Status von next_state zu ändern, erstellen Sie __ "go ()" __, das __ Ziel __ aus Status und Richtung definiert. -Die Funktion __ "take_single_action ()" __, die den nächsten Zustand basierend auf der Übergangswahrscheinlichkeit bestimmt, wird auch hier verwendet. Der "nächste Zustand" wird aktualisiert, bis die im obigen "T ()" definierte "Übergangswahrscheinlichkeit" x überschreitet und die Belohnung am Ende der Aktualisierung festgelegt ist.

• Erstellen Sie abschließend eine Funktion __ "move ()" __, die sich tatsächlich "2 Mal vom aktuellen Status nach oben und 3 Mal nach rechts" bewegt. Als Aktionen definiert die __0. Spalte die Auf- und Abbewegung, die 1. Spalte die Links- und Rechtsbewegung __, bewegt sich zweimal mit take_single_action für die 0. Spalte und bewegt sich dreimal für die 1. Spalte, um den Status zu aktualisieren. ..

・ Ausführungsteil

・ Jede Zelle ist für die Umgebung definiert. Sie können auch den Anfangsposition und den Endpunkt definieren und mit move () den Status nach dem Verschieben ermitteln.

Sarsa ・ Sarsa ist eine der TD-Methoden und löst __Bellman-Gleichung __ durch Versuch und Irrtum. Bei der Wertiteration usw. wurde $ V (s) $ verwendet, aber hier wird __ Aktionswertfunktion $ Q (s, a) $ verwendet __. Diese Q-Funktion wird durch ein Array von __ [alle Zustände x alle Aktionen] __ dargestellt.

• In Bezug auf "alle Zustände" zu diesem Zeitpunkt gibt es in Umgebung 2 11 mögliche Zustände und 4 "alle Aktionen" nach oben, unten, links und rechts. Daher möchte ich die Q-Funktion zu einem 11x4-Array machen, aber da der __Zustand durch Koordinaten __ dargestellt wird, kann dies nicht gut ausgedrückt werden. Daher ist der Zustandsteil der __ "x-Koordinate x 10 + y-Koordinate x 1" __ zugeordnet.

-Der spezifische Code lautet wie folgt. (Der Teil, der sich mit dem vorherigen Abschnitt überschneidet, wird weggelassen.)

-__ "Get_action ()" __ ist eine Funktion, die die Aktion basierend auf dem Maximalwert der später definierten Q-Funktion (q_table) __ bestimmt. Der zu diesem Zeitpunkt übergebene __ "t_state" __ ist der oben beschriebene __ "Zustand mit konvertierten Koordinaten" . - "Take_single_action ()" __ hat den gleichen Zweck wie der vorherige, aber wenn die Belohnung nicht als zurückgegebener Wert festgelegt ist, dh wenn sich das Aktionsziel __ aufgrund einer Wand oder eines Hindernisses nicht bewegen kann __ , Gibt den Status "state" und die Belohnung "-0.04" im Sinne eines Stopps an Ort und Stelle zurück und gibt "next_state" und seine Belohnung auf dem Feld zurück, auf dem die Belohnung festgelegt ist. - "update_qtable ()" __ ist eine Funktion, die die aktionswertfunktion Q tatsächlich berechnet und aktualisiert. Die zum Zeitpunkt dieses Updates verwendete Formel lautet: $Q(s,a) += \alpha[r + \gamma Q(s',a') - Q(s,a)]$

・ Diese $ \ alpha $ ist Lernrate und muss im Voraus festgelegt werden. Diesmal mit __ "0.4" __ einstellen. Der Abzinsungssatz $ \ gamma $ beträgt __ "0,8" __. Außerdem wird der zu diesem Zeitpunkt übergebene Zustand auch als "Zustand, in dem Koordinaten konvertiert werden" bezeichnet. Die Berechnung selbst kann nach der Formel erfolgen.

• Erstellen Sie abschließend eine __ "trans_state ()" __ - Funktion, die den Status "state" in "state with konvertierten Koordinaten" ändert.

・ Ausführungsteil

-Wenn Sie Sarsa ausführen, initialisieren Sie zuerst die aktionswertfunktion Q. Dieses Mal beträgt die Anzahl der Episoden 500, der Zeitschritt maximal 1000 Mal und __ "Die durchschnittliche Belohnung beträgt 5 aufeinanderfolgende Male 0,7 oder mehr" __ wird als Endbedingung für die Episode festgelegt. Bereiten Sie daher ein Array vor, um dies zu verwalten. Die Umgebung ist dieselbe wie im vorherigen Abschnitt. -Nächste wiederholen Sie für jede der 500 Folgen alles nach __ (bis die Endbedingung erfüllt ist) __. ・ Initialisieren Sie zuerst __state __. Darauf basierend werden der "t_state" und die Aktion "action" berechnet, die an die Q-Funktion übergeben werden sollen. Verwenden Sie die Funktionen "trans_state ()" und "get_action ()". ・ Als nächstes erhalten Sie für jeden Zeitschritt in der Episode den nächsten Status und die Belohnung r, wenn die Aktion a mit __ "take_single_action ()" __ ausgeführt wird, und sammeln Sie __ Belohnungen __ Ich werde gehen. Außerdem werden für den Zustand s 'der "t_next_state" und die Aktion "next_action" berechnet, die an die Q-Funktion übergeben werden sollen. -Pass diese an __ "update_qtable ()" __, um die __Aktionswertfunktion __ zu aktualisieren. Aktualisieren Sie auch den Status und die Aktion, um mit dem nächsten Zeitschritt fortzufahren. ・ Wenn Sie den Endpunkt erreicht haben, endet diese Episode und Sie fahren mit der nächsten Episode fort. Aktualisieren Sie vor dem Verschieben __ "total_reward_vec" für die Belohnung, die die Endbedingung der Episode darstellt, und geben Sie sie aus. In ähnlicher Weise wird die Nummer der beendeten Episode und die Anzahl der Schritte ausgegeben. ・ Wenn der __Mindestwert __ dieses "total_reward_vec" 0,7 überschreitet, endet die Wiederholung der Episode.

-Ausführungsergebnis (nur Teil)

• Mit Blick auf die Ausführungsergebnisse wurden Episoden mit einer Belohnung von "0,2" aus den letzten 5 Episoden ausgeschlossen, und alle Belohnungen endeten in Episode 21 + 1 mit mehr als 0,7.

Implementierung der ε-gierigen Methode in Sarsa

-In der Methode im vorherigen Abschnitt wurde nur der Maximalwert der Q-Funktion ausgewählt, aber dabei besteht die Gefahr, dass eine bessere Methode als __ übersehen wird. Um dies zu vermeiden, werden wir mit der __ε-gierigen Methode __ nach neuen Methoden suchen. ・ Obwohl in Kapitel 1 die ε-gierige Methode verwendet wurde, wird sie mit einer geringfügigen Änderung verwendet. Dieses Mal verwenden wir die Methode __ "Erhöhen Sie ε, um das Suchverhältnis zu erhöhen, während die Episode früh ist, und verringern Sie den Wert von ε, um die Suche im Verlauf der Episode einzugrenzen." Das Folgende wird als Formel verwendet. $\epsilon = 0.5 * (1 / ( episode + 1)) $

-Der spezifische Code lautet wie folgt: Nur der Teil "get_action ()" unterscheidet sich.

-Für die obige Funktion berechnen Sie zuerst "epsilon" mit der obigen Formel. Wenn dieses Epsilon kleiner oder gleich der einheitlichen Zufallszahl "np.random.uniform (0,1)" ist, __ bestimmen Sie die nächste Aktion basierend auf dem Maximalwert der Q-Funktion wie im vorherigen Abschnitt __, andernfalls. __ Entscheide dich zufällig für die nächste Aktion __.

・ Ausführungsteil

• Obwohl der Ausführungsteil fast derselbe wie im vorherigen Abschnitt ist, wird die zu Beginn definierte __ "Aktion" __ anhand des Maximalwerts der Q-Funktion bestimmt, ohne dass get_action () mit Zufallszahlen angewendet wird. .. Diese Funktion wird für next_action verwendet.

Q Lernen

-Es gibt eine TD-Methode namens __ "Q learning" __, die sich von Sarsa unterscheidet. Es ist im Grunde dasselbe wie Sarsa, aber der Unterschied besteht darin, dass bei der Verarbeitung jedes Zeitschritts die __Q-Funktion die Q-Funktion aktualisiert, nachdem die nächste Aktion __ bestimmt wurde. Q-Lernen ist __, das die nächste Aktion nach dem Update entscheidet.

• Übergeben Sie daher __ "next_action" ___ nicht an die Funktion __ "update_Qtable ()" __, sondern berechnen Sie stattdessen den Maximalwert "next_max_q" __ der __Q-Funktion in next_state und verwenden Sie ihn. Aktualisieren Sie die Q-Funktion. Davon abgesehen ist es genau das gleiche wie Sarsa.

Zusammenfassung

-Wenn das Modell der Umgebung bei der Bestimmung von Markov vollständig angegeben wird, wird die Methode zur Ermittlung der optimalen Richtlinie unter Verwendung der Belman-Gleichung in Kapitel 2 als "dynamische Planungsmethode (Dynamic Planning Method, DP)" bezeichnet.

• Die Berechnung der Wertfunktion $ V ^ \ pi (s) $ bei Verwendung einer bestimmten Methode $ \ pi $ wird als Richtlinienbewertung bezeichnet. Darüber hinaus ist bekannt, dass die Wertfunktion größer wird, wenn die Greedy-Methode angewendet wird, und dies wird als Wertverbesserung bezeichnet. Die optimale Methode kann durch wiederholte Bewertung und Verbesserung gefunden werden. Dies wird als Richtlinienwiederholung bezeichnet.
• Als Anwendung der Richtlinieniteration wird die Methode zum Aktualisieren der Wertfunktion zur Berechnung des Werts anstelle der Richtlinie als Wertiteration bezeichnet. Dadurch kann der Rechenaufwand für die Wertefunktion erheblich reduziert werden.
• Da Richtlinieniteration und Wertiteration dynamische Planungsmethoden sind und nur für Modelle mit einer Zustandsübergangsrate verwendet werden können, wird die TD-Methode für Modelle verwendet, für die dies nicht angegeben ist. TD-Methoden umfassen Sarsa- und Q-Lernen. ・ Berücksichtigen Sie beim Lernen von Sarsa und Q die optimale Richtlinie, indem Sie die Aktionswertfunktion Q mithilfe der Belman-Gleichung berechnen.

Diese Zeit ist vorbei. Vielen Dank für das Lesen bis zum Ende.