Serie über Reinforcement Studying (RL), im Anschluss an Suttons und Bartos berühmtes Buch „Reinforcement Studying“ (1).
In den vorherigen Beiträgen haben wir die Analyse von Teil I dieses Buches abgeschlossen, in dem grundlegende Lösungstechniken vorgestellt werden, die die Grundlage für viele RL-Methoden bilden. Diese sind: Dynamische Programmierung (DP), Monte-Carlo-Methoden (MC) Und Zeitdifferenzlernen (TD). Was Teil I von Teil II von Suttons Buch unterscheidet und die Unterscheidung rechtfertigt, ist eine Einschränkung der Problemgröße: Während in Teil I tabellarische Lösungsmethoden behandelt wurden, wagen wir uns nun, tiefer in dieses faszinierende Thema einzutauchen und die Funktionsnäherung einzubeziehen.
Um es konkret zu machen: In Teil I haben wir angenommen, dass der Zustandsraum der untersuchten Probleme klein genug ist, damit wir ihn und auch die gefundenen Lösungen über eine einfache Tabelle darstellen können (stellen Sie sich eine Tabelle vor, die für jeden Zustand eine bestimmte „Güte“ – einen Wert – angibt). Nun geben wir in Teil II diese Annahme auf und sind somit in der Lage, beliebige Probleme anzugehen.
Und dieses modifizierte Setup ist dringend notwendig, wie wir aus erster Hand beobachten konnten: In einem früheren Beitrag gelang es uns, Tic Tac Toe zu lernen, scheiterte aber bereits an Join 4 – da die Anzahl der Staaten hier in der Größenordnung von 10²⁰ liegt. Oder stellen Sie sich ein RL-Downside vor, das eine Aufgabe basierend auf Kamerabildern lernt: Die Anzahl der möglichen Kamerabilder ist größer als die Anzahl der Atome im bekannten Universum (1).
Diese Zahlen sollten jeden davon überzeugen, dass Näherungslösungsverfahren unbedingt notwendig sind. Sie ermöglichen nicht nur die Bewältigung solcher Probleme, sondern bieten auch eine Verallgemeinerung: Bei tabellarischen Methoden wurden zwei nahe beieinander liegende, aber dennoch unterschiedliche Zustände völlig getrennt behandelt – während wir bei Näherungslösungsverfahren hoffen würden, dass unsere Funktionsnäherung solche nahe beieinander liegenden Zustände erkennen und verallgemeinern kann.
Damit fangen wir an. In den nächsten Absätzen werden wir:
- Geben Sie eine Einführung in die Funktionsnäherung
- Lösungsmethoden für solche Probleme entwickeln
- Diskutieren Sie verschiedene Möglichkeiten für Näherungsfunktionen.
Einführung in die Funktionsnäherung
Im Gegensatz zu tabellarischen Lösungsverfahren, bei denen wir beispielsweise eine Tabelle zur Darstellung von Wertfunktionen verwendet haben, verwenden wir jetzt eine parametrisierte Funktion
mit einem Gewichtsvektor
v kann alles sein, beispielsweise eine lineare Funktion der Eingabewerte oder ein tiefes neuronales Netzwerk. Später in diesem Beitrag werden wir verschiedene Möglichkeiten im Element besprechen.
Normalerweise ist die Anzahl der Gewichte viel kleiner als die Anzahl der Zustände – was zu einer Verallgemeinerung führt: Wenn wir unsere Funktion durch Anpassen einiger Gewichte aktualisieren, aktualisieren wir nicht nur einen einzelnen Eintrag in einer Tabelle – sondern dies hat Auswirkungen auf (möglicherweise) auch alle anderen Schätzungen.
Lassen Sie uns die Aktualisierungsregeln einiger der Methoden zusammenfassen, die wir in früheren Beiträgen gesehen haben.
MC-Methoden weisen die beobachtete Rendite G als Wertschätzung für einen Zustand zu:
TD(0) führt einen Bootstrapping der Wertschätzung des nächsten Zustands durch:
Während DP Folgendes verwendet:
Von nun an interpretieren wir Aktualisierungen der Type s -> u als Enter/Output-Paare einer Funktion, die wir approximieren möchten, und nutzen hierfür Techniken des maschinellen Lernens, insbesondere: Supervised Studying. Aufgaben, bei denen Zahlen (u) geschätzt werden müssen, werden als Funktionsnäherung oder Regression bezeichnet.
Um dieses Downside zu lösen, können wir theoretisch auf jede mögliche Methode für eine solche Aufgabe zurückgreifen. Wir werden dies gleich noch besprechen, sollten aber erwähnen, dass an solche Methoden bestimmte Anforderungen gestellt werden: Zum einen sollten sie in der Lage sein, inkrementelle Änderungen und Datensätze zu verarbeiten – da wir in RL normalerweise im Laufe der Zeit Erfahrungen sammeln, die sich beispielsweise von klassischen überwachten Lernaufgaben unterscheiden. Darüber hinaus sollte die gewählte Methode in der Lage sein, mit instationären Zielen umzugehen – worauf wir im nächsten Unterabschnitt eingehen werden.
Das Vorhersageziel
Im gesamten ersten Teil von Suttons Buch brauchten wir nie ein Vorhersageziel oder ähnliches – schließlich konnten wir immer auf die optimale Funktion konvergieren, die den Wert jedes Zustands perfekt beschreibt. Aus den oben genannten Gründen ist dies nicht mehr möglich und erfordert die Definition eines Ziels, einer Kostenfunktion, die wir optimieren möchten.
Wir verwenden Folgendes:
Versuchen wir, das zu verstehen. Hierbei handelt es sich um eine Erwartung hinsichtlich der Differenz zwischen vorhergesagten und tatsächlichen Werten, die intuitiv sinnvoll ist und beim überwachten Lernen üblich ist. Beachten Sie, dass wir dazu eine Verteilung µ definieren müssen, die angibt, wie wichtig uns bestimmte Zustände sind.
Oftmals handelt es sich dabei einfach um ein Maß, das proportional dazu ist, wie oft Staaten besucht werden – die On-Coverage-Verteilung, auf die wir uns in diesem Abschnitt konzentrieren werden.
Beachten Sie jedoch, dass eigentlich nicht klar ist, ob dies das richtige Ziel ist: Bei RL geht es uns darum, gute Richtlinien zu finden. Einige unserer Methoden können das oben genannte Ziel zwar sehr intestine optimieren, das vorliegende Downside aber dennoch nicht lösen – z. B. wenn die Richtlinie zu viel Zeit in unerwünschten Zuständen verbringt. Dennoch brauchen wir, wie besprochen, ein solches Ziel – und mangels anderer Möglichkeiten optimieren wir dieses einfach.
Als nächstes stellen wir eine Methode zur Minimierung dieses Ziels vor.
Minimierung des Vorhersageziels
Das von uns für diese Aufgabe ausgewählte Werkzeug ist Stochastic Gradient Descent (SGD). Im Gegensatz zu Sutton möchte ich hier nicht zu sehr ins Element gehen und mich nur auf den RL-Teil konzentrieren – daher möchte ich den interessierten Leser auf (1) oder ein anderes Tutorial zum Thema SGD/Deep Studying verweisen.
Aber im Prinzip verwendet SGD Batches (oder Mini-Batches), um den Gradienten des Ziels zu berechnen und die Gewichte einen kleinen Schritt in Richtung Minimierung dieses Ziels zu aktualisieren.
Für diesen Gradienten gilt additionally:
Nun der interessante Teil: Nehmen Sie an, dass v_π nicht das wahre Ziel ist, sondern eine (verrauschte) Annäherung daran, sagen wir U_t:
Wir können zeigen, dass, wenn U_t ein erwartungstreuer Wert von v_π ist, die über SGD erhaltene Lösung zu einem lokalen Optimum konvergiert – praktisch. Wir können jetzt einfach z. B. die MC-Rückgabe als U_t verwenden und unsere allererste Gradienten-RL-Methode erhalten:
Es ist auch möglich, andere Maße für U_t zu verwenden, insbesondere auch Bootstrapping zu verwenden, additionally frühere Schätzungen zu verwenden. Dabei verlieren wir diese Konvergenzgarantien – aber wie so oft empirisch funktioniert das trotzdem. Solche Methoden werden Semigradientenmethoden genannt, da sie nur die Auswirkung der Änderung der Gewichte auf den zu aktualisierenden Wert berücksichtigen, nicht jedoch auf das Ziel.
Auf dieser Grundlage können wir TD(0) mit Funktionsnäherung einführen:
Eine natürliche Erweiterung davon und ebenfalls eine Erweiterung der entsprechenden n-stufigen Tabellenmethode ist die n-stufige Halbgradienten-TD:
Methoden zur Funktionsnäherung
Im Relaxation von Kapitel 9 beschreibt Sutton verschiedene Arten der Darstellung der Näherungsfunktion: Ein großer Teil des Kapitels befasst sich mit der linearen Funktionsnäherung und dem Merkmalsdesign dafür, und für die nichtlineare Funktionsnäherung werden künstliche neuronale Netze eingeführt. Wir werden diese Themen nur kurz behandeln, da wir in diesem Weblog hauptsächlich mit (tiefen) neuronalen Netzen und nicht mit einfachen linearen Approximationen arbeiten und außerdem vermuten, dass der aufmerksame Leser bereits mit den Grundlagen von Deep Studying und neuronalen Netzen vertraut ist.
Lineare Funktionsnäherung
Lassen Sie uns dennoch kurz auf die lineare Approximation eingehen. Dabei wird die Zustandswertfunktion durch das innere Produkt angenähert:
Hier wird der Zustand durch den Vektor beschrieben
– und wie wir sehen können, ist dies ein linear Kombination der Gewichte.
Aufgrund der Einfachheit der Darstellung gibt es einige elegante Formeln (und Darstellungen mit geschlossenem Regelkreis) für die Lösung sowie einige Konvergenzgarantien.
Merkmalskonstruktion für lineare Methoden
Eine Einschränkung der oben eingeführten naiven linearen Funktionsnäherung besteht darin, dass jedes Merkmal separat verwendet wird und keine Kombination von Merkmalen möglich ist. Als Beispiel nennt Sutton die problematische Karrenstange: Hier können hohe Winkelgeschwindigkeiten je nach Kontext intestine oder schlecht sein. Wenn die Stange intestine zentriert ist, sollte man schnelle, ruckartige Bewegungen wahrscheinlich vermeiden. Je näher die Stange jedoch dem Umfallen kommt, desto höhere Geschwindigkeiten sind möglicherweise erforderlich.
Es gibt daher einen separaten Forschungszweig zum Entwurf effizienter Merkmalsdarstellungen (obwohl man argumentieren könnte, dass dies aufgrund des Aufkommens von Deep Studying an Bedeutung verliert).
Eine solche Darstellung ist Polynome. Stellen Sie sich als einführendes Beispiel vor, dass der Zustandsvektor aus zwei Teilen besteht, s_1 und s_2. Wir könnten den Merkmalsraum folgendermaßen definieren:
Dann könnten wir mit dieser Darstellung immer noch eine lineare Funktionsnäherung durchführen – additionally vier Gewichte für die vier neu konstruierten Merkmale verwenden und insgesamt immer noch eine lineare Funktion bezüglich der Gewichte haben.
Allgemeiner gesagt, die Polynombasismerkmale der Ordnung n+1 dargestellt werden kann durch
wobei die cs ganze Zahlen in {0 … n} sind.
Andere häufig verwendete Basen sind die Fourier-Foundation, die Grob- und Kachelkodierung sowie radiale Basisfunktionen – aber wie bereits erwähnt, werden wir an dieser Stelle nicht näher darauf eingehen.
Abschluss
In diesem Beitrag haben wir über die vorherigen Beiträge hinaus einen wichtigen Schritt hin zur Bereitstellung von RL-Algorithmen „in freier Wildbahn“ gemacht. In den vorangegangenen Beiträgen haben wir uns auf die Einführung der wesentlichen RL-Methoden konzentriert, allerdings in Type tabellarischer Methoden. Wir haben gesehen, dass sie bei größeren Problemen schnell an ihre Grenzen stoßen und haben daher erkannt, dass Näherungslösungsmethoden erforderlich sind.
In diesem Beitrag haben wir Grundlagen dafür vorgestellt. Diese Methoden ermöglichen nicht nur die Bewältigung großer, realer Probleme, sondern führen auch die Verallgemeinerung ein – eine wichtige Notwendigkeit für jeden erfolgreichen RL-Algorithmus.
Wir begannen mit der Einführung eines geeigneten Prognoseziels und Möglichkeiten, dieses zu optimieren.
Dann haben wir unsere ersten Gradienten- und Halbgradienten-RL-Algorithmen für das Vorhersageziel eingeführt – das heißt, eine Wertfunktion für eine bestimmte Richtlinie zu lernen.
Abschließend haben wir verschiedene Möglichkeiten zur Konstruktion der Näherungsfunktion besprochen.
Wie immer vielen Dank fürs Lesen! Und wenn Sie interessiert sind, bleiben Sie gespannt auf den nächsten Beitrag, in dem wir uns mit dem entsprechenden Steuerungsproblem befassen.
Weitere Beiträge dieser Serie
Referenzen