Q-Learning

In der künstlichen Intelligenz , genauer gesagt im maschinellen Lernen , ist Q-Learning eine verstärkende Lerntechnik . Diese Technik erfordert kein anfängliches Modell der Umgebung . Der Buchstabe 'Q' bezeichnet die Funktion, die die Qualität einer in einem bestimmten Zustand des Systems ausgeführten Aktion misst.

Beschreibung

Mit dieser Lernmethode können Sie eine Richtlinie lernen, die angibt, welche Aktion in den einzelnen Systemzuständen ausgeführt werden soll. Es funktioniert durch Lernen einer notierten Zustandsaktionswertfunktion , die den potenziellen Gewinn, d. H. Die langfristige Belohnung , bestimmt, die durch Ausführen einer bestimmten Aktion in einem bestimmten Zustand durch Befolgen einer optimalen Richtlinie erzielt wird. Wenn diese Aktionsstatuswertfunktion dem Agenten bekannt / gelernt ist, kann die optimale Richtlinie konstruiert werden, indem die Maximalwertaktion für jeden Zustand ausgewählt wird, d. H. Indem die Aktion ausgewählt wird , die den Wert maximiert, wenn sich der Agent im Status befindet .

Eine der Stärken des Lernens besteht darin, dass es möglich ist, die wahrscheinlichen Vorteile des Ergreifens der zugänglichen Maßnahmen zu vergleichen, ohne über anfängliche Kenntnisse der Umgebung zu verfügen . Mit anderen Worten, obwohl das System als Markov-Entscheidungsprozess modelliert ist (abgeschlossen), lernt der Agent nicht, es zu wissen, und der Algorithmus - das Lernen verwendet es nicht.

Dieser Begriff des Belohnungslernens wurde ursprünglich 1989 in Watkins 'These eingeführt. Er ist eine Variante des Lernens zeitlicher Unterschiede. In der Folge wurde bewiesen, dass - Lernen zu einer optimalen Politik konvergiert, dh zur Maximierung der Gesamtbelohnung der aufeinanderfolgenden Stufen führt.

Algorithmus

Die Situation besteht aus einem Agenten, einer Reihe von Zuständen und Aktionen . Durch Ausführen einer Aktion wechselt der Agent von einem Status in einen neuen Status und erhält eine Belohnung (dies ist ein numerischer Wert). Das Ziel des Agenten ist es, seine Gesamtbelohnung zu maximieren. Dies wird erreicht, indem für jeden Zustand die optimale Aktion gelernt wird. Die optimale Aktion für jeden Staat ist die mit der größten langfristigen Belohnung. Diese Belohnung ist die gewichtete Summe der mathematischen Erwartung der Belohnungen jedes zukünftigen Schritts aus dem aktuellen Zustand. Das Gewicht jedes Schritts kann sein, wobei die Verzögerung zwischen dem aktuellen und dem zukünftigen Schritt und eine Zahl zwischen 0 und 1 (dh ) als Abzinsungsfaktor bezeichnet wird .

Der Algorithmus berechnet eine Aktionszustandswertfunktion:

Bevor das Lernen beginnt, wird die Funktion willkürlich initialisiert. Dann beobachtet der Agent bei jeder Auswahl der Aktion die Belohnung und den neuen Status (der vom vorherigen Status und der aktuellen Aktion abhängt). Das Herzstück des Algorithmus ist eine Aktualisierung der Wertefunktion . Die Definition der Wertefunktion wird bei jedem Schritt wie folgt aktualisiert:

Wo ist der neue Zustand, ist der vorherige Zustand, ist die gewählte Aktion, ist die Belohnung, die der Agent erhalten hat, ist eine Zahl zwischen 0 und 1, die als Lernfaktor bezeichnet wird , und ist der Aktualisierungsfaktor .

Eine Episode des Algorithmus endet, wenn es sich um einen Endzustand handelt. Allerdings - Lernen kann auch auf nicht-episodische Aufgaben angewandt werden. Wenn der Abzinsungsfaktor kleiner als 1 ist, ist der Aktionszustandswert selbst für unendlich endlich .

NB: Für jeden Endzustand wird der Wert von niemals aktualisiert und behält seinen Anfangswert bei. Normalerweise wird auf Null initialisiert.

Pseudocode

Hier ist der Pseudocode des Q-Lernens.

initialiser Q[s, a] pour tout état s, toute action a de façon arbitraire, mais Q(état terminal, a) = 0 pour toute action a répéter //début d'un épisode initialiser l'état s répéter //étape d'un épisode choisir une action a depuis s en utilisant la politique spécifiée par Q (par exemple ε-greedy) exécuter l'action a observer la récompense r et l'état s' Q[s, a] := Q[s, a] + α[r + γ maxa' Q(s', a') - Q(s, a)] s := s' a := a' jusqu'à ce que s soit l'état terminal

Einfluss von Variablen auf den Algorithmus

Lernfaktor

Der Lernfaktor bestimmt, um wie viel die neu berechneten Informationen die alten übertreffen. Wenn = 0, lernt der Agent nichts. Wenn umgekehrt = 1, ignoriert der Agent immer alles, was er gelernt hat, und berücksichtigt nur die letzte Information.

In einer deterministischen Umgebung ist die Lerngeschwindigkeit optimal. Wenn das Problem stochastisch ist, konvergiert der Algorithmus unter bestimmten Bedingungen abhängig von der Lerngeschwindigkeit. In der Praxis entspricht diese Geschwindigkeit häufig der gesamten Dauer des Prozesses.

Abzinsungsfaktor

Der Abzinsungsfaktor γ bestimmt die Größe zukünftiger Belohnungen. Ein Faktor von 0 würde den Agenten kurzsichtig machen, indem nur die aktuellen Belohnungen berücksichtigt werden, während ein Faktor nahe 1 auch die weiter entfernten Belohnungen einbringen würde. Wenn der Abzinsungsfaktor nahe oder gleich 1 ist, kann der Wert von abweichen.

Erweiterungen und Varianten

Doppeltes Q- Lernen

Da Q- Learning den Maximalschätzer verwendet, überschätzt Q- Learning den Wert von Aktionen und daher ist das Lernen in lauten Umgebungen langsam. Dieses Problem wird in der Variante gelöst, die als doppeltes Q- Lernen bezeichnet wird und zwei Bewertungsfunktionen verwendet und aus zwei verschiedenen Erfahrungssätzen gelernt wird. Das Update erfolgt kreuzweise:

, und

Da der geschätzte Wert mit einer anderen Richtlinie bewertet wird, ist das Problem der Überschätzung gelöst. Das Erlernen des eingestellten Algorithmus kann mithilfe von Deep-Learning-Techniken erfolgen, was zu DQNs ( Deep Q-Networks ) führt. Wir können dann Double DQN verwenden, um eine bessere Leistung als mit dem ursprünglichen DQN-Algorithmus zu erzielen.

Anmerkungen und Referenzen

  1. Tambet Matiisen , „  Deep Reinforcement Learning entmystifizieren | Computational Neuroscience Lab  ” , auf neuro.cs.ut.ee ,19. Dezember 2015(abgerufen am 6. April 2018 )
  2. CJ Watkins, Lernen aus verspäteten Belohnungen , Kings College, Cambridge, Mai 1989
  3. (in) George F Luger, Künstliche Intelligenz: Strukturen und Strategien zur komplexen Problemlösung. 5. Auflage. , Addison Wesley,2005903  p. ( ISBN  0-321-26318-9 , online lesen ) , p. 448
  4. Watkins und Dayan, Q-Learning. Maschinelles Lernen , 1992
  5. (in) David L. Poole und Alan K. Mackworth , Künstliche Intelligenz , Cambridge University Press ,2009( ISBN  978-0-511-79479-7 , DOI  10.1017 / CBO9780511794797 , online lesen ) , p. 469
  6. Reinforcement Learning: Eine Einführung , Richard Sutton und Andrew Barto, MIT Press, 1998.
  7. (in) Stuart J. Russell und Peter Norvig , Künstliche Intelligenz: Ein moderner Ansatz , Prentice Hall ,2010, Third  ed. 1132  p. ( ISBN  978-0-13-604259-4 ) , p.  649
  8. Hado van Hasselt , "  Double Q-Learning  ", Fortschritte in neuronalen Informationsverarbeitungssystemen , vol.  23,2011, p.  2613–2622 ( online lesen [PDF] )
  9. Hado van Hasselt , Arthur Guez und David Silver , „  Tiefenverstärkungslernen mit doppeltem Q-Lernen  “, AAAI-Konferenz über künstliche Intelligenz ,2015, p.  2094–2100 ( online lesen [PDF] )
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">