Markov-Entscheidungsprozesse und bestärkendes Lernen

Ein Markov-Entscheidungsprozess, kurz MDP, beschreibt wiederholte Entscheidungen, wenn Aktionen ungewisse Ergebnisse haben können. Der Agent beobachtet seinen aktuellen Zustand, wählt eine verfügbare Aktion, erhält eine Belohnung und geht in einen neuen Zustand über. Diese vier Bestandteile beschreiben einen Übergang; eine Folge von Übergängen beschreibt einen Durchlauf.

Lies ein Übergangsmodell

Die Zustandsmenge ist $S$, und $A(s)$ führt die im Zustand $s$ erlaubten Aktionen auf. Das Übergangsmodell $T(s,a,s^{\mathrm{\prime }})=P(s^{\mathrm{\prime }}\mid s,a)$ gibt die Wahrscheinlichkeit an, nach Aktion $a$ in $s$ den Zustand $s^{\mathrm{\prime }}$ zu erreichen. Für jedes Zustands-Aktions-Paar sind alle diese Wahrscheinlichkeiten nichtnegativ und ergeben zusammen 1. Die Belohnung $R(s,a,s^{\mathrm{\prime }})$ gehört zu diesem Übergang. Eine negative Belohnung stellt Kosten oder eine Strafe dar.

Betrachte einen Lieferroboter mit den Zuständen Akkustand Hoch, Akkustand Niedrig und Leer. Leer beendet die Episode. Sein Modell lautet:

Die Wahrscheinlichkeiten in den beiden Zeilen für Arbeiten ergeben jeweils zusammen 1. Für Arbeiten in Niedrig beträgt die erwartete unmittelbare Belohnung $\mathrm{0,6}(4)+\mathrm{0,4}(-10)=-\mathrm{1,6}$. Dieser Mittelwert ist für die Planung nützlich, ein tatsächlicher Versuch bringt aber entweder 4 oder −10. Die Wahl von Arbeiten legt die Verteilung fest, nicht das erfolgreiche Ergebnis.

Nimm die relevante Vergangenheit in den Zustand auf

Die Markov-Eigenschaft bedeutet, dass der aktuelle Zustand und die aktuelle Aktion die Information enthalten, die nötig ist, um den nächsten Zustand vorherzusagen:

Die Welt kann eine lange Vorgeschichte haben. Diese Vorgeschichte wirkt sich über die Variablen aus, die im aktuellen Zustand enthalten sind. Die Position eines Roboters allein reicht möglicherweise nicht aus, wenn sein Akkustand bestimmt, ob ein Auftrag gelingt. Bezieht das Modell den Akkustand ein, kann es Situationen mit unterschiedlichen Risiken unterscheiden.

Ein üblicher MDP setzt voraus, dass der Agent den Zustand genau beobachtet. Sind wichtige Teile des Zustands verborgen, braucht der Agent eine Wahrscheinlichkeitsverteilung über mögliche Zustände; das führt zu einem partiell beobachtbaren MDP, kurz POMDP.

Erkenne Endzustände und zufällige Bewegungen

Ein Terminalzustand hat den Wert 0, weil ihm keine Belohnungen folgen. Die Belohnung beim Eintritt zählt weiterhin: Der Roboter erhält −10 für seinen letzten Übergang nach Leer. Episodische Aufgaben enden in einem Terminalzustand; fortlaufende Aufgaben wie die dauerhafte Temperaturregelung brauchen keinen Terminalzustand.

In einer Gitterwelt kann eine beabsichtigte Bewegung mit Wahrscheinlichkeit 0,8 gelingen und mit jeweils Wahrscheinlichkeit 0,1 in eine der beiden senkrechten Richtungen abrutschen. Der Versuch, sich in eine Wand zu bewegen, lässt den Agenten stehen. Die Wahrscheinlichkeiten von Ergebnissen, die dasselbe Feld erreichen, müssen zusammengefasst werden.

Deterministische Übergänge sind ein Spezialfall: Ein Nachfolger hat Wahrscheinlichkeit 1. Bei bekanntem Anfangszustand und einer geeigneten Aufgabe, bei der ein Ziel erreicht werden soll, kann ein fester Plan ausreichen. Bei ungewissen Ergebnissen legt eine Strategie fest, wie in dem Zustand zu reagieren ist, der tatsächlich eintritt. Manche Texte schreiben Belohnungen als $R(s)$ oder $R(s,a)$; prüfe die zeitliche Konvention, bevor du eine Formel überträgst.

Eine Strategie beschreibt, wie der Agent handelt. Eine deterministische stationäre Strategie $\pi (s)$ wählt für jeden Zustand eine Aktion und behält diese Wahl über die Zeit bei. Für den Roboter ist „Arbeiten bei Hoch, Laden bei Niedrig“ eine solche Strategie. Eine stochastische Strategie $\pi (a\mid s)$ ordnet den verfügbaren Aktionen Wahrscheinlichkeiten zu.

Berechne eine Gesamtbelohnung

Die diskontierte Gesamtbelohnung fasst die Belohnungen eines Durchlaufs zusammen:

Der erste Übergang bringt $r_0$ mit dem Gewicht 1. Jede spätere Belohnung erhält einen weiteren Faktor des Diskontierungsfaktors $\gamma$. Für die Belohnungen −1, −1, −1 und +10 mit anschließendem Ende ergibt sich mit $\gamma =\mathrm{0,9}$

Mit $\gamma =\mathrm{0,5}$ ergibt derselbe Durchlauf $-1-\mathrm{0,5}-\mathrm{0,25}+10(\mathrm{0,125})=-\mathrm{0,5}$. Der spätere Gewinn verliert einen großen Teil seines Gewichts. Diskontierung kann eine Vorliebe für frühere Belohnungen oder die Wahrscheinlichkeit darstellen, dass der Prozess um einen weiteren Schritt fortgesetzt wird.

Eine Strategie wird anhand ihrer erwarteten Gesamtbelohnung beurteilt, gemittelt über ihre möglichen Durchläufe. Ein glücklicher Durchlauf beweist nicht, dass eine Strategie gut ist. Eine optimale Strategie ${\pi }^{\ast }$ ergibt von jedem Zustand aus die größte erwartete Gesamtbelohnung. Ein endlicher diskontierter MDP besitzt eine optimale Strategie, die deterministisch und stationär ist.

Halte eine unendliche Zukunft endlich

Bei beschränkten Belohnungen und $0\le \gamma <1$ begrenzt die geometrische Reihe jede Gesamtbelohnung. Gilt $\mathrm{\mid }{r}_t\mathrm{\mid }\le R_{\max }$, dann gilt

Die betragsmäßig größte Belohnung des Roboters ist 10, also ergibt $\gamma =\mathrm{0,9}$ die Schranke $\mathrm{\mid }U\mathrm{\mid }\le 100$. Da seine größte positive Belohnung 4 ist, kann seine Gesamtbelohnung außerdem $4\mathrm{/}(1-\mathrm{0,9})=40$ nicht überschreiten. Das sind Schranken, keine Aussagen darüber, dass der Roboter sie erreichen kann.

Die Größe $1\mathrm{/}(1-\gamma )$ ist ein grober effektiver Planungshorizont: etwa 10 Schritte für $\gamma =\mathrm{0,9}$. Sie ist keine Abbruchgrenze. Eine Belohnung 10 Schritte später erhält weiterhin das Gewicht ${\mathrm{0,9}}^{10}\approx \mathrm{0,35}$. Undiskontierte fortlaufende Aufgaben erfordern besondere Vorsicht: Wiederholte positive Belohnungen können Gesamtbelohnungen unendlich machen. Ein fester endlicher Planungshorizont macht die Summe endlich; episodische Modelle brauchen für endliche Erwartungswerte außerdem geeignete Episodenlängen.

Berücksichtige Zeit und Schrittbelohnungen bei Entscheidungen

Bei einer Frist kann die beste Aktion von der verbleibenden Zeit abhängen. Betrachte eine Maschine im Zustand Abgenutzt. Betrieb bringt 6 und lässt sie mit gleicher Wahrscheinlichkeit Abgenutzt oder Defekt zurück. Reparatur bringt −4 und versetzt sie in den Zustand Gut. In Gut bringt Betrieb 10; in Defekt bringt Reparatur −20. Bei einem verbleibenden Schritt ist Betrieb in Abgenutzt besser: $6>-4$. Bei zwei verbleibenden Schritten und $\gamma =\mathrm{0,9}$ ergibt Reparatur $-4+\mathrm{0,9}(10)=5$. Betrieb ergibt $6+\mathrm{0,9}[\mathrm{0,5}(6)+\mathrm{0,5}(-20)]=-\mathrm{0,3}$. Durch die zusätzliche Zeit kehrt sich die Wahl um.

Die Schrittbelohnung einer Gitterwelt, die für nichtterminale Schritte vergeben wird, verändert die Kosten einer Verzögerung. Negative Schrittbelohnungen begünstigen das Erreichen eines Ausgangs; eine größere Strafe kann einen nahen schlechten Ausgang gegenüber einem langen Weg vorziehen lassen. Eine ausreichend große positive Schrittbelohnung kann den Aufenthalt im Gitter begünstigen. Die genaue Wahl hängt auch von Diskontierung, Entfernungen und Abrutschrisiken ab.

Die Formulierung eines MDP überführt ein praktisches Ziel in Entscheidungen, die ein Computer bewerten kann. Lege zunächst fest, wann Entscheidungen getroffen werden. Definiere dann einen beobachtbaren Zustand, zulässige Aktionen, Übergangswahrscheinlichkeiten, Belohnungen, gegebenenfalls Terminalzustände sowie einen Diskontierungsfaktor oder Planungshorizont. Die Qualität der resultierenden Strategie hängt von diesen Entscheidungen ab.

Modelliere die Maschinenwartung

Angenommen, eine Maschine wird einmal pro Entscheidungsschritt geprüft. Ihr Zustand ist Gut, Abgenutzt oder Defekt. Das Modell lautet:

Defekt ist nicht terminal: Eine Reparatur ermöglicht die Fortsetzung der Arbeit. Die Aufgabe ist fortlaufend, mit $\gamma =\mathrm{0,9}$. Beachte, dass die verfügbaren Aktionen vom Zustand abhängen; in Defekt ist Betrieb nicht verfügbar.

Das Lösen dieses Modells ergibt optimale Werte von etwa 78,64 in Gut, 66,78 in Abgenutzt und 50,78 in Defekt. In Abgenutzt hat Reparatur den Wert $-4+\mathrm{0,9}(\mathrm{78,64})\approx \mathrm{66,78}$. Betrieb hat den Wert $6+\mathrm{0,9}[\mathrm{0,5}(\mathrm{66,78})+\mathrm{0,5}(\mathrm{50,78})]\approx \mathrm{58,90}$. Die negative unmittelbare Belohnung für die Reparatur erkauft den Zugang zu einer produktiveren Zukunft.

Wähle genügend Zustandsinformationen

Der Zustand muss Vorhersagen sowohl der Ergebnisse als auch der Belohnungen ermöglichen. Die Position eines bewegten Balls allein lässt seine Geschwindigkeit aus, sodass zwei identische Positionen unterschiedliche nächste Positionen haben können. Eine Brettspielstellung muss auch enthalten, wer am Zug ist. Ändert die verbleibende Zeit, welche Aktionen sich lohnen, nimm sie in eine Entscheidungsregel mit endlichem Planungshorizont auf oder ergänze den Zustand um sie.

Zusätzliche Variablen vergrößern den Zustandsraum. Zehn Ja-Nein-Variablen erlauben $2^{10}=1024$ Kombinationen. Behalte Informationen, die Vorhersagen oder Belohnungen verändern; die Speicherung der gesamten Vorgeschichte kann ein handhabbares Modell unnötig groß machen. Der übliche stationäre MDP setzt voraus, dass die Übergangs- und Belohnungsregeln über die Zeit gleich bleiben. Ein verborgener Zustand verlangt ein Modell der Wahrscheinlichkeiten möglicher Zustände, strategische Gegner dagegen ein Spielmodell.

Lass die Belohnung das Ziel ausdrücken

Ein Reinigungsroboter, der für jedes eingesammelte Schmutzstück belohnt wird, kann davon profitieren, Schmutz zu verteilen und erneut einzusammeln. Das ist Reward Hacking: die erfolgreiche Optimierung eines schlechten Maßes. Eine an die gewünschte Sauberkeit gebundene Belohnung vermeidet genau diese Schleife. Eine spärliche Zielbelohnung beschreibt den Erfolg klar, liefert aber während eines langen Versuchs wenig Rückmeldung.

Reward Shaping ergänzt Rückmeldungen über den Fortschritt. Willkürliche Boni können das Ziel verändern. Zwei nützliche Vergleiche:

• Die Multiplikation aller Belohnungen mit derselben positiven Zahl erhält die Rangfolge der Strategien.
• Die Addition einer Konstante zu jeder Belohnung erhält bei einer fortlaufenden diskontierten Aufgabe die optimalen Strategien, weil jede Strategie dieselbe diskontierte Konstante hinzugewinnt. Bei einer episodischen Aufgabe gewinnen längere und kürzere Durchläufe unterschiedlich viel hinzu, sodass sich die Rangfolge ändern kann.

Ein Shaping-Term, der die Strategien erhält, hat die Form $F(s,a,s^{\mathrm{\prime }})=\gamma \mathrm{\Phi }(s^{\mathrm{\prime }})-\mathrm{\Phi }(s)$. Dabei ordnet $\mathrm{\Phi }$ jedem Zustand ein Potenzial zu. Bei beschränkten Potenzialen in einer fortlaufenden diskontierten Aufgabe heben sich die zusätzlichen diskontierten Terme bis auf einen vom Anfangszustand abhängigen Term auf. Setzt du bei episodischen Aufgaben jedes terminale Potenzial auf 0, entfällt der verbleibende terminale Term. Ein terminales Potenzial ungleich null kann ändern, welches Ende oder welcher Endzeitpunkt bevorzugt wird.

Ein Wert misst die Gesamtbelohnung, die aus einer Situation bei einer bestimmten Verhaltensweise erreichbar ist. Er umfasst zukünftige Belohnungen, gewichtet nach ihren Wahrscheinlichkeiten und Zeitpunkten. Dadurch unterscheiden sich Werte von der Belohnung für einen einzelnen Übergang.

Unterscheide die erste Wahl

Der Zustandswert $V^{\pi }(s)$ ist die erwartete diskontierte Gesamtbelohnung, wenn der Agent im Zustand $s$ startet und der Strategie $\pi$ folgt. Der Aktionswert $Q^{\pi }(s,a)$ legt die erste Aktion auf $a$ fest und folgt danach $\pi$. Das bedeutet nicht, dass bei jedem späteren Schritt $a$ ausgeführt wird.

Optimale Werte ersetzen diese Fortsetzungsstrategie durch das bestmögliche Verhalten. Somit ist $V^{\ast }(s)$ die beste erwartete Gesamtbelohnung ab $s$ und $Q^{\ast }(s,a)$ die beste erwartete Gesamtbelohnung nach Festlegung der ersten Aktion. Ihr Zusammenhang lautet

Das Maximum ist eine Zahl; das Argmax bezeichnet eine Aktion, die es erreicht. Erreichen mehrere Aktionen dasselbe Maximum, kann jede von ihnen gewählt werden.

Interpretiere die Entscheidungen des Roboters

Für den Lieferroboter mit $\gamma =\mathrm{0,9}$ lauten die optimalen Q-Werte:

Das Maximum jeder Zeile ist der optimale Wert des Zustands. In Hoch ist Arbeiten besser, in Niedrig Laden. Laden bringt unmittelbar 0, ermöglicht in Niedrig aber wieder den Zugang zu Hoch und dessen besseren Zukunftsaussichten. Arbeiten in Niedrig hat dennoch einen positiven optimalen Q-Wert, weil ein Roboter, dessen Akku durchhält, danach laden kann.

Die Fortsetzungsstrategie ist entscheidend. Unter „immer Arbeiten“ fallen die Zustandswerte auf etwa 8,27 in Hoch und −3,48 in Niedrig. Das Modell hat sich nicht geändert; geändert haben sich die Entscheidungen nach jedem Ergebnis. Eine Zahl, die nur als „der Wert“ bezeichnet wird, ist unvollständig, solange die gemeinte Strategie oder Optimalität nicht klar ist.

Betrachte Entscheidungen und Zufall als getrennte Ebenen

Ein Expectimax-Baum wechselt zwischen zwei Arten von Knoten. In einem Zustand wählt der Agent eine Aktion; bei einem Zustands-Aktions-Paar, manchmal Q-Zustand genannt, wählt der Zufall den nächsten Zustand gemäß dem Übergangsmodell. Der Agent maximiert über Aktionen und mittelt über deren Ergebnisse.

Ein zyklischer MDP wiederholt dieselben Zustände an vielen Stellen des Baums. Dynamische Programmierung speichert für jeden Zustand einen Wert und verwendet ihn wieder. So muss dasselbe Fortsetzungsproblem nicht jedes Mal neu berechnet werden, wenn ein Pfad im Baum zu diesem Zustand zurückkehrt.

Leite aus den verfügbaren Werten eine Strategie ab

Vergleiche bei einer Q-Tabelle die Aktionswerte in der aktuellen Zeile. Ein Übergangsmodell ist nicht nötig. Berechne bei allein vorliegenden Zustandswerten zunächst die erwartete Belohnung einer Aktion zuzüglich des diskontierten Werts des Nachfolgers:

Diese Rechnung braucht Übergänge und Belohnungen. Wählst du lediglich die Aktion, die den Nachfolger mit dem höchsten Wert erreichen kann, ignorierst du, wie wahrscheinlich dieser Nachfolger ist und was die Aktion kostet. Auch bei einem hohen Erwartungswert bleibt ein unglücklicher Durchlauf möglich: Der Wert beschreibt einen Mittelwert über Ergebnisse und keine garantierte Belohnung bei jedem Versuch.

Die Gesamtbelohnung eines Durchlaufs lässt sich nach seinem ersten Übergang aufteilen: in die unmittelbare Belohnung und die diskontierte Gesamtbelohnung ab dem nächsten Zustand. Durch Bildung eines Erwartungswerts entsteht eine Bellman-Gleichung. Sie verknüpft den Wert eines Zustands mit den Werten seiner Nachfolger und berücksichtigt dabei auch die Möglichkeit, in denselben Zustand zurückzukehren.

Bewerte eine festgelegte Strategie

Für eine deterministische Strategie erscheint nur die von ihr gewählte Aktion:

Jeder Zweig trägt seine Wahrscheinlichkeit mal der Summe aus unmittelbarer Belohnung und zukünftigem Wert bei. Es gibt eine Gleichung pro Zustand. In einem endlichen diskontierten MDP sind dies lineare Gleichungen mit einer eindeutigen Lösung.

Beginne bei der Roboterstrategie „immer Arbeiten“ in Niedrig. Die beiden möglichen Übergänge ergeben

Multipliziere aus und fasse die Unbekannte zusammen: $V(L)=\mathrm{2,4}+\mathrm{0,54}V(L)-4$, also $\mathrm{0,46}V(L)=-\mathrm{1,6}$. Daher gilt $V(L)\approx -\mathrm{3,48}$. Die Belohnung −10 bleibt bestehen, obwohl der zukünftige Wert von Leer 0 ist.

In Hoch bringen beide Ergebnisse 4, ihre unmittelbaren Belohnungen ergeben zusammen also 4:

Das Zusammenfassen der Terme ergibt $\mathrm{0,37}V(H)=4+\mathrm{0,27}V(L)$. Verwendest du den ungerundeten Wert für Niedrig, erhältst du $V(H)\approx \mathrm{8,27}$. Runde beim Einsetzen die Zwischenergebnisse nicht; runde die angegebenen Werte erst am Ende.

Ergänze die Wahl der Aktion

Berechne für optimale Werte den Erwartungswert jeder verfügbaren Aktion und nimm dann den besten:

Das Maximum steht außerhalb der Summe, weil der Agent eine Aktion wählt, bevor er das Ergebnis sieht. Würde er für jeden möglichen Folgezustand eine andere aktuelle Aktion wählen, hätte er Informationen, über die er noch nicht verfügt.

Die Q-Form legt diese erste Aktion fest, erlaubt aber nach Beobachtung des Nachfolgers die beste nächste Aktion:

Diese Optimalitätsgleichungen enthalten Maxima, lassen sich also nicht direkt durch einmaliges Lösen eines linearen Gleichungssystems für eine festgelegte Strategie lösen.

Prüfe vorgeschlagene Werte

Verwende die vorgeschlagenen optimalen Werte des Roboters $V(H)\approx \mathrm{31,50}$ und $V(L)\approx \mathrm{28,35}$. In Hoch ergibt Arbeiten $4+\mathrm{0,9}[\mathrm{0,7}(\mathrm{31,50})+\mathrm{0,3}(\mathrm{28,35})]\approx \mathrm{31,50}$. Laden ergibt $\mathrm{0,9}(\mathrm{31,50})=\mathrm{28,35}$. Das größere Ergebnis stimmt mit dem vorgeschlagenen Wert für Hoch überein.

In Niedrig ergibt Arbeiten $\mathrm{0,6}[4+\mathrm{0,9}(\mathrm{28,35})]+\mathrm{0,4}(-10)\approx \mathrm{13,71}$; Laden ergibt 28,35. Auch dieses Maximum stimmt mit dem vorgeschlagenen Wert für Niedrig überein. Würdest du nur einen Zustand prüfen, bliebe die andere Gleichung ungeprüft. Kleine Abweichungen sind zu erwarten, wenn die vorgeschlagenen Werte gerundet wurden.

Diskontiere nur den Term für die Zukunft. Ersetzt du $R+\gamma V$ durch $\gamma (R+V)$, verschiebst du die unmittelbare Belohnung fälschlich um einen Schritt.

Die Strategiebewertung fragt, wie viel erwartete Gesamtbelohnung eine festgelegte Strategie einbringt. Das Modell und die Strategie sind bekannt. Während dieser Rechnung werden keine Aktionsentscheidungen verbessert; das Ergebnis ist $V^{\pi }$, das später einen getrennten Verbesserungsschritt unterstützen kann.

Löse die Gleichungen exakt

Nimm die Strategie „Arbeiten bei Hoch, Laden bei Niedrig“ und $\gamma =\mathrm{0,9}$. Laden in Niedrig bringt keine unmittelbare Belohnung und führt immer zu Hoch, also $V(L)=\mathrm{0,9}V(H)$. Arbeiten in Hoch ergibt

Setze die erste Gleichung in die zweite ein:

Dann gilt $\mathrm{0,127}V(H)=4$, woraus $V(H)=4\mathrm{/}\mathrm{0,127}\approx \mathrm{31,50}$ und $V(L)\approx \mathrm{28,35}$ folgen. Damit sind die Werte dieser Strategie bestimmt. Um ihre Optimalität zu beweisen, musst du auch konkurrierende Aktionen prüfen.

Die exakte Bewertung löst eine lineare Gleichung pro nichtterminalem Zustand. Ein übliches Eliminationsverfahren für eine dicht besetzte Matrix benötigt ungefähr $\mathrm{\mid }S{\mathrm{\mid }}^3$ Rechenoperationen. Für ein kleines Modell ist das Verfahren praktisch, weil sich die Zusammenhänge direkt untersuchen lassen.

Bewerte durch wiederholte Durchläufe

Eine iterative Alternative beginnt mit $V_0(s)=0$ und wendet die Aktualisierung für die festgelegte Strategie auf jeden Zustand an:

Jeder neue Wert nutzt das alte Array. Für „immer Arbeiten“ ergeben die ersten drei Durchläufe in der Reihenfolge Hoch, dann Niedrig:

Der zweite Wert für Niedrig ist zum Beispiel $\mathrm{0,6}[4+\mathrm{0,9}(-\mathrm{1,6})]+\mathrm{0,4}(-10)=-\mathrm{2,464}$. Hoch nutzt in demselben Durchlauf den alten Wert 4 für Hoch und den alten Wert −1,6 für Niedrig. Das ergibt $4+\mathrm{0,9}[\mathrm{0,7}(4)+\mathrm{0,3}(-\mathrm{1,6})]=\mathrm{6,088}$.

Bei einem Diskontierungsfaktor unter 1 konvergieren die Durchläufe gegen etwa 8,27 und −3,48. Ein Durchlauf für eine festgelegte Strategie mit dicht besetztem Übergangsmodell benötigt ungefähr $\mathrm{\mid }S{\mathrm{\mid }}^2$ Rechenoperationen, weil für jeden Zustand über Nachfolger summiert wird. Bei dünn besetzten Übergangsmodellen lassen sich Nachfolger mit Wahrscheinlichkeit 0 überspringen.

Interpretiere Zwischenwerte

Bei Startwerten von null ist $V_k(s)$ die erwartete diskontierte Belohnung über die nächsten $k$ Übergänge unter der festgelegten Strategie, ohne Wert jenseits dieses Horizonts. Der erste Durchlauf sieht nur unmittelbare Belohnungen. Der zweite bezieht einen weiteren Übergang ein. Diese Zwischenwerte haben auch vor der Konvergenz eine klare Bedeutung.

Bei der Aktualisierung an Ort und Stelle werden innerhalb desselben Durchlaufs einige frisch berechnete Werte genutzt. Unter den üblichen Bedingungen für Diskontierung kann auch dieses Verfahren konvergieren, seine Zwischenarrays müssen aber nicht diesen synchronen Werten für endliche Planungshorizonte entsprechen. Halte bei einer Rechnung von Hand alte und neue Arrays getrennt, wenn du synchrone Durchläufe vergleichst.

Ergänze während der Bewertung kein Maximum über Aktionen. Dadurch könnte der Agent sein Verhalten ändern, und die Rechnung würde eine andere Frage beantworten als die, die die festgelegte Strategie vorgibt.

Die Wertiteration fragt wiederholt, was am besten ist, wenn eine weitere Entscheidung möglich ist. Sie beginnt mit $V_0=0$ und aktualisiert jeden Zustandswert auf die beste erwartete Belohnung zuzüglich des diskontierten Werts des Nachfolgers. Dieselbe Rechnung bewältigt Zyklen, weil die Nachfolgerwerte aus einem gespeicherten Array stammen.

Führe einen vollständigen Durchlauf aus

Berechne für jeden nichtterminalen Zustand

Im ersten Durchlauf des Roboters sind alle Terme für die Zukunft 0. In Hoch wird Arbeiten mit 4 mit Laden mit 0 verglichen, also $V_1(H)=4$. In Niedrig wird Arbeiten mit $\mathrm{0,6}(4)+\mathrm{0,4}(-10)=-\mathrm{1,6}$ mit Laden mit 0 verglichen, also $V_1(L)=0$.

Der zweite Durchlauf nutzt dieses gesamte alte Array. In Hoch ergibt Arbeiten $4+\mathrm{0,9}[\mathrm{0,7}(4)+\mathrm{0,3}(0)]=\mathrm{6,52}$, Laden dagegen $\mathrm{0,9}(4)=\mathrm{3,6}$. In Niedrig ergibt Arbeiten weiterhin −1,6, Laden dagegen 3,6. Somit gilt $V_2=(\mathrm{6,52};\mathrm{3,6})$. Ein dritter Durchlauf ergibt etwa $(\mathrm{9,08};\mathrm{5,87})$.

Würde der neue Wert 6,52 für Hoch sofort zur Aktualisierung von Niedrig genutzt, wäre das Ergebnis anders. Das wäre eine Aktualisierung an Ort und Stelle, nicht der gerade gezeigte synchrone zweite Durchlauf.

Verstehe, was konvergiert

Bei Initialisierung mit null ist $V_k$ die optimale erwartete Gesamtbelohnung bei genau $k$ verbleibenden Entscheidungsmöglichkeiten, wobei terminale Episoden früher enden können. Jeder Durchlauf erweitert den nutzbaren Planungshorizont um eins. Der Bellman-Optimalitätsoperator ist für $\gamma <1$ eine Kontraktion: Der größte Fehler über alle Zustände schrumpft bei jeder Anwendung mindestens um den Faktor $\gamma$. Die Werte konvergieren von jedem endlichen Anfangsarray aus gegen das eindeutige $V^{\ast }$.

Ein Durchlauf mit dicht besetztem Modell betrachtet Zustände, Aktionen und Nachfolger und benötigt ungefähr $\mathrm{\mid }S{\mathrm{\mid }}^2\mathrm{\mid }A\mathrm{\mid }$ Rechenoperationen. Ein Diskontierungsfaktor nahe 1 verlangsamt die Konvergenz meist, weil weit entfernte Belohnungen mehr Gewicht behalten.

Halte mit einer Fehlerschranke an

Sei ${\mathrm{\Delta }}_k={\max }_s\mathrm{\mid }{V}_{k+1}(s)-V_k(s)\mathrm{\mid }$. Für $0<\gamma <1$ ist der maximale Fehler des neuen Arrays durch $\gamma {\mathrm{\Delta }}_k\mathrm{/}(1-\gamma )$ beschränkt. Um einen Fehler unter einer gewählten Toleranz $\epsilon$ sicherzustellen, genügt

Für $\gamma =\mathrm{0,9}$ und die Toleranz 0,01 beträgt die Schwelle etwa 0,00111. Eine Änderung unter 0,01 allein garantiert keinen Wertefehler unter 0,01. Bei $\gamma =0$ ergibt eine einzige Aktualisierung die optimalen unmittelbaren Belohnungen, sodass keine Division durch den Diskontierungsfaktor nötig ist.

Lies die Strategie ab

Vergleiche nach dem Anhalten die Erwartungswerte der Aktionen mit dem endgültigen Wertearray. Diese Einschrittvorausschau ergibt eine gierige Strategie. Die Strategie kann sich vor den Werten stabilisieren: Die gierige Strategie des Roboters aus $V_1$ lautet bereits „Arbeiten bei Hoch, Laden bei Niedrig“, seine Werte brauchen aber 77 Durchläufe, um sich dem optimalen Paar $(\mathrm{31,50};\mathrm{28,35})$ bis auf 0,01 zu nähern.

Eine stabil erscheinende Strategie und genaue Werte sind unterschiedliche Prüfungen. Die Aktualisierung muss für jede Aktion die erwarteten Ergebnisse vergleichen; die Wahl des einzelnen wertvollsten möglichen Nachfolgers lässt sowohl das Risiko als auch die unmittelbare Belohnung außer Acht.

Die Strategieiteration wechselt zwischen zwei Aufgaben: Sie misst eine Strategie und verbessert dann anhand dieser Messung deren Aktionen. Beginne mit einer beliebigen deterministischen Strategie. Eine gute anfängliche Vermutung kann Arbeit sparen, ist aber für die Korrektheit in einem endlichen diskontierten MDP nicht erforderlich.

Trenne Bewertung und Verbesserung

Berechne zunächst $V^{{\pi }_i}$, die Werte der aktuellen Strategie. Vergleiche dann für jeden Zustand alle Aktionen anhand derselben Werte:

Die Bewertung beschreibt das alte Verhalten. Die Verbesserung fragt, ob eine Änderung der ersten Aktion die Gesamtbelohnung verbessern würde, wenn danach der alten Strategie gefolgt würde. Änderst du alle entsprechenden Aktionen, erhältst du eine Strategie, die in jedem Zustand mindestens genauso gut ist. Ist die alte Strategie nicht optimal, gibt es in mindestens einem Zustand eine echte Verbesserung.

Behalte die aktuelle Aktion bei, wenn sie zu den besten gehört. Andernfalls können gleich gute Aktionen den Eindruck erwecken, dass sich eine Strategie ständig ändert, obwohl sich der Wert nicht verbessert.

Verbessere die Strategie des Roboters

Beginne mit „immer Arbeiten“. Die exakte Bewertung ergibt für Hoch etwa 8,27 und für Niedrig etwa −3,48. In Hoch ergibt das Beibehalten von Arbeiten 8,27; der Wechsel zu Laden ergibt $\mathrm{0,9}(\mathrm{8,27})\approx \mathrm{7,45}$. Behalte Arbeiten bei. In Niedrig ergibt Arbeiten −3,48 und Laden etwa 7,45. Wechsle in Niedrig zu Laden.

Bewerte nun die neue Strategie „Arbeiten bei Hoch, Laden bei Niedrig“. Ihre Werte betragen etwa 31,50 und 28,35. Verbessere erneut:

Keine Aktion ändert sich, also endet die Strategieiteration. Die Werte der festgelegten Strategie erfüllen auch die Optimalitätsgleichungen, womit ihre Optimalität nachgewiesen ist. Ausgehend von dieser Anfangsstrategie brauchte der Roboter zwei vollständige Bewertungen.

Erkläre, warum das Verfahren endet

Ein endlicher MDP hat nur endlich viele deterministische Strategien. Hat jeder der $\mathrm{\mid }S\mathrm{\mid }$ Zustände jeweils $\mathrm{\mid }A\mathrm{\mid }$ Wahlmöglichkeiten, gibt es $\mathrm{\mid }A{\mathrm{\mid }}^{\mathrm{\mid }S\mathrm{\mid }}$ solche Strategien. Der Roboter hat zwei nichtterminale Zustände mit jeweils zwei Aktionen, also $2^2=4$ Strategien. Durch echte Verbesserung, wann immer nötig, und eine einheitliche Behandlung von Gleichständen kann das Verfahren nicht zu einer schlechteren Strategie zurückkehren und muss enden.

Vergleiche die Planungsverfahren

Vollständige Bewertungen machen die Runden der Strategieiteration aufwendiger, aber oft sind weniger Runden nötig. Die 77 Wertiterationsdurchläufe und zwei Strategiebewertungen des Roboters sind unterschiedliche Arbeitseinheiten; die Anzahlen allein zeigen daher nicht, welches Verfahren schneller ist. Nutze bei jeder Verbesserung Werte, die zur aktuellen Strategie gehören; vermischst du sie mit Werten einer vorherigen Strategie, verliert dieser Schritt seine Bedeutung.

Beim bestärkenden Lernen lernt ein Agent in einem Entscheidungsproblem aus Erfahrung. Er beobachtet einen Zustand, wählt eine verfügbare Aktion und erhält eine Stichprobe $(s,a,r,s^{\mathrm{\prime }})$: den vorherigen Zustand, die Aktion, die Belohnung und den nächsten Zustand. Das Ziel bleibt eine hohe erwartete Gesamtbelohnung, aber Übergangswahrscheinlichkeiten und Belohnungen müssen gelernt werden.

Trenne Lernen und Planung

Planung nutzt ein MDP-Modell, um Werte oder Strategien zu berechnen. Sie kann vor dem Handeln stattfinden oder während der Agent im Betrieb erneut plant. Lernen nutzt beobachtete Erfahrungen, entweder aus laufender Interaktion oder aus einem zuvor gesammelten Datensatz. Auch bestärkendes Offline-Lernen lernt aus Erfahrung; es nutzt aufgezeichnete Erfahrungen.

Beim passiven Lernen ist eine Strategie festgelegt und die Aufgabe besteht darin, ihre Leistung zu schätzen. Beim aktiven Lernen wählt der Agent auch Aktionen, um besseres Verhalten zu entdecken. Diese Entscheidungen beeinflussen sowohl die gesammelte Belohnung als auch die für künftige Aktualisierungen verfügbaren Informationen.

Schätze Übergänge anhand von Häufigkeiten

Ein modellbasiert lernender Agent erfasst, wie oft jede Aktion in jedem Zustand ausprobiert wird. Sei $N(s,a)$ die Anzahl dieser Versuche und $N(s,a,s^{\mathrm{\prime }})$ die Anzahl der Versuche, die in einem bestimmten Nachfolger enden. Dann gilt

Die Häufigkeiten im Zähler teilen die Versuche im Nenner auf die Nachfolger auf, sodass ihre geschätzten Wahrscheinlichkeiten zusammen 1 ergeben. Bei einem nicht ausprobierten Paar ist der Nenner 0. Es braucht mehr Erfahrung oder eine ausdrückliche Modellierungsentscheidung; eine empirische Übergangsverteilung liegt noch nicht vor.

Beim Roboter wurde Arbeiten in Hoch 20-mal ausprobiert: 13 Übergänge blieben in Hoch und 7 erreichten Niedrig. Die Schätzungen sind $13\mathrm{/}20=\mathrm{0,65}$ und $7\mathrm{/}20=\mathrm{0,35}$. Arbeiten in Niedrig wurde 10-mal ausprobiert: 7-mal hielt der Akku durch und 3-mal wurde Leer erreicht, was 0,7 und 0,3 ergibt. Die zweite Schätzung unterschätzt die tatsächliche Wahrscheinlichkeit 0,4, Leer zu erreichen.

Erfasse auch die Belohnungen für jeden Übergang. Der Roboter hat feste Belohnungen für seine Ergebnisse. Sind die Belohnungen bei wiederholten identischen Übergängen verrauscht, schätze ihre bedingte mittlere Belohnung aus den beobachteten Stichproben.

Plane mit dem gelernten Modell

Nutze die geschätzten Übergänge und Belohnungen in der Wertiteration oder Strategieiteration. Für diese Häufigkeiten des Roboters, bei bekannten Übergängen für Laden und $\gamma =\mathrm{0,9}$, betragen die geschätzten optimalen Werte etwa $(\mathrm{30,42};\mathrm{27,38})$. Die optimalen Aktionsentscheidungen stimmen weiterhin mit dem tatsächlichen Modell überein: Arbeiten in Hoch, Laden in Niedrig. Ähnliche Strategien können also aus unterschiedlichen Wertschätzungen entstehen.

Wenige Stichproben können ungenaue Modelle ergeben. Mehr repräsentative Erfahrung verbessert die Schätzungen, aber wenn Daten nur unter einer eng begrenzten Strategie gesammelt werden, können nützliche Aktionen unversucht bleiben. Auch ein modellbasiert lernender Agent braucht Exploration.

Vergleiche zwei Lernwege

Ein gelerntes Modell kann Stichproben für viele Planungsaktualisierungen wiederverwenden und eine erneute Planung bei veränderten Zielen unterstützen. Es benötigt aber auch Speicher und Rechenaufwand, und Modellfehler können den Plan verzerren. Modellfreie Verfahren vermeiden den Aufbau einer Übergangstabelle, brauchen aber meist viel Erfahrung, damit ihre Wertschätzungen zuverlässig werden.

Eine festgelegte Strategie lässt sich bewerten, ohne ihr Übergangsmodell zu kennen. Die direkte Bewertung mittelt vollständige beobachtete Gesamtbelohnungen. Das Lernen mit zeitlichen Differenzen, kurz TD-Lernen, aktualisiert anhand einer einzelnen Belohnung und eines geschätzten Nachfolgerwerts. Beide lernen die Werte der Strategie aus Erfahrung.

Mittle Gesamtbelohnungen ganzer Episoden

Folge „immer Arbeiten“ mit $\gamma =\mathrm{0,9}$. Eine Roboter-Episode lautet Hoch → Hoch (+4), Hoch → Niedrig (+4), Niedrig → Leer (−10). Die Gesamtbelohnungen ab den Besuchen von Hoch sind $4+\mathrm{0,9}(4)+\mathrm{0,81}(-10)=-\mathrm{0,5}$ und $4+\mathrm{0,9}(-10)=-5$. Die Gesamtbelohnung ab Niedrig ist −10.

Eine zweite Episode lautet Hoch → Niedrig (+4), Niedrig → Niedrig (+4), Niedrig → Leer (−10). Ihre Gesamtbelohnung ab Hoch ist −0,5; ihre Gesamtbelohnungen ab Niedrig sind −5 und −10. Die Mittelwerte des Every-Visit-Verfahrens sind daher $(-\mathrm{0,5}-5-\mathrm{0,5})\mathrm{/}3=-2$ für Hoch und $(-10-5-10)\mathrm{/}3\approx -\mathrm{8,33}$ für Niedrig. Ein First-Visit-Verfahren würde nur den ersten Besuch eines Zustands in jeder Episode zählen.

Diese Schätzungen unterscheiden sich stark von den tatsächlichen Strategiewerten $(\mathrm{8,27};-\mathrm{3,48})$, weil beide Episoden schnell endeten. Vollständige Gesamtbelohnungen unterliegen Stichprobenschwankungen. Bei genügend vielen repräsentativen abgeschlossenen Episoden nähern sich ihre Mittelwerte den erwarteten Gesamtbelohnungen der Strategie. Die direkte Bewertung wartet, bis die benötigte Gesamtbelohnung am Ende der Episode vorliegt, und schätzt Zustände getrennt voneinander.

Aktualisiere nach einem Übergang

TD nutzt die aktuelle Schätzung dessen, was folgt:

Der Zielwert ist $r+\gamma V(s^{\mathrm{\prime }})$. Der TD-Fehler ist der Zielwert minus der aktuellen Schätzung. Die Lernrate $\alpha$ steuert, welcher Anteil dieses Fehlers für die Aktualisierung genutzt wird.

Angenommen, $V(H)=10$, $V(L)=8$, $\gamma =\mathrm{0,9}$ und $\alpha =\mathrm{0,5}$. Nach Hoch → Niedrig mit Belohnung 4 ist der Zielwert $4+\mathrm{0,9}(8)=\mathrm{11,2}$. Der Fehler ist $\mathrm{11,2}-10=\mathrm{1,2}$, also ist die neue Schätzung für Hoch $10+\mathrm{0,5}(\mathrm{1,2})=\mathrm{10,6}$. Der gespeicherte Wert für Niedrig bleibt bei dieser Aktualisierung 8. Ein terminaler Folgezustand trägt keinen Term für die Zukunft bei.

TD nutzt Bootstrapping: Es verwendet eine Schätzung, um eine andere zu verbessern. Das gibt Informationen durch verbundene Zustände weiter und ermöglicht Aktualisierungen bei fortlaufenden Aufgaben, frühe Zielwerte können aber durch schlechte Nachfolgerschätzungen verzerrt sein.

Steuere, wie stark neue Beobachtungen zählen

Eine große Lernrate reagiert stark auf jeden Zielwert. Bei $\alpha =1$ wird die alte Schätzung durch den neuesten Zielwert ersetzt. Eine feste positive Rate folgt im Allgemeinen weiterhin dem Stichprobenrauschen. Geeignet abnehmende Raten unterstützen bei wiederholten Besuchen und den üblichen Annahmen für endliche diskontierte Probleme die Konvergenz von tabellarischem TD. Eine Rate $1\mathrm{/}N(s)$ mittelt die Folge der beobachteten TD-Zielwerte; diese Zielwerte ändern sich selbst, wenn sich die Nachfolgerschätzungen verbessern.

Zustandswerte allein zeigen ohne Übergangs- und Belohnungsinformationen für eine Vorausschau nicht die beste Aktion. Passives TD bewertet das Verhalten, das seine Stichproben erzeugt. Das Lernen von Aktionswerten gibt einem Agenten eine direkte Möglichkeit, Aktionen zu vergleichen, ohne zuerst ein Modell zu lernen.

Q-Lernen lernt Aktionswerte aus beobachteten Übergängen. Sein Zielwert setzt die beste nächste Aktion voraus, selbst während der Agent explorierende Aktionen wählt. So kann er lernen, gut zu handeln, ohne ein Übergangsmodell zu schätzen.

Ersetze eine erwartete Aktualisierung durch eine Stichprobe

Eine modellbasierte Q-Aktualisierung mittelt über alle möglichen Nachfolger:

Q-Lernen sieht jeweils einen Nachfolger. Nach einer Stichprobe $(s,a,r,s^{\mathrm{\prime }})$ berechnet es

und aktualisiert $Q(s,a)\leftarrow Q(s,a)+\alpha [y-Q(s,a)]$. Bei einem terminalen Nachfolger gilt $y=r$. Das Maximum wird über die im nächsten Zustand verfügbaren Aktionen gebildet, nicht über die im gerade verlassenen Zustand.

Initialisiere die Q-Tabelle, wähle eine Aktion nach einer Explorationsregel, beobachte das Ergebnis, aktualisiere den gewählten Eintrag und fahre vom nächsten Zustand aus fort. Starte nach dem Ende erneut. Um die gelernte Strategie zu nutzen, wähle eine Aktion, die den größten Q-Wert in der aktuellen Zeile erreicht.

Rechne zwei Aktualisierungen durch

Seien $\gamma =\mathrm{0,9}$ und $\alpha =\mathrm{0,5}$. Anfangs gilt $Q(L,\text{Arbeiten})=5$. Der Roboter probiert Arbeiten in Niedrig und erreicht Leer mit Belohnung −10. Der Zielwert ist −10, also ist der neue Wert $5+\mathrm{0,5}(-10-5)=-\mathrm{2,5}$. Nach Leer gibt es keine zukünftige Gesamtbelohnung.

Angenommen, als Nächstes gilt $Q(H,\text{Arbeiten})=6$ und der Roboter arbeitet in Hoch, erhält 4 und erreicht Niedrig. In Niedrig sind die Schätzungen −2,5 für Arbeiten und 3 für Laden. Der beste nächste Wert ist 3, sodass der Zielwert $4+\mathrm{0,9}(3)=\mathrm{6,7}$ beträgt. Der aktualisierte Wert für Hoch und Arbeiten ist $6+\mathrm{0,5}(\mathrm{6,7}-6)=\mathrm{6,35}$. Diese Stichprobe aktualisiert nur diesen Tabelleneintrag.

Unterscheide Zielverhalten und tatsächliches Verhalten

Q-Lernen ist Off-Policy: Die Fortsetzung in seinem Zielwert ist gierig, auch wenn seine Aktionsauswahl exploriert. SARSA ist On-Policy: Es nutzt $r+\gamma Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }})$ für die tatsächlich als Nächstes gewählte Aktion.

In der Nähe einer Klippe kann ein explorierender Agent versehentlich gefährliche Schritte machen. SARSA berücksichtigt diese zukünftigen explorierenden Aktionen und kann einen vorsichtigeren Weg lernen. Q-Lernen zielt auf die gierige Fortsetzung und kann einen kürzeren Weg an der Kante bevorzugen, auch wenn die Exploration seine Trainingsdurchläufe riskant macht.

Gib die tabellarische Garantie genau an

In einem endlichen stationären MDP mit beschränkten Belohnungen und $\gamma <1$ konvergiert tabellarisches Q-Lernen mit Wahrscheinlichkeit 1 gegen $Q^{\ast }$, wenn jedes Zustands-Aktions-Paar unendlich viele Aktualisierungen erhält und seine Lernraten erfüllen:

Eine Rate $1\mathrm{/}N(s,a)$ pro Paar hat diese Form. Eine Rate $1\mathrm{/}N(s,a{)}^2$ nimmt zu schnell ab: Ihre Gesamtsumme ist endlich, sodass möglicherweise zu wenig Anpassung bleibt, um einen anfänglichen Fehler zu beseitigen. Eine unendliche Gesamtanpassung verhindert, dass das Lernen zu früh endet; eine endliche Summe der quadrierten Anpassungen begrenzt angesammeltes Rauschen. Konstante Raten führen bei stochastischen Aufgaben im Allgemeinen zu anhaltenden Schwankungen. Dies sind Bedingungen für den Grenzfall, sodass ein endlicher Trainingslauf weiterhin bewertet werden muss.

Exploitation wählt die Aktion, die aktuell am besten erscheint. Exploration sammelt Informationen, die eine bessere Wahl aufdecken können. Wenn ein früher unglücklicher Versuch mit Arbeiten dazu führt, dass der Roboter in Hoch Laden bevorzugt, kann reine Exploitation ihn dauerhaft laden lassen und die Schätzung für Arbeiten unkorrigiert bleiben.

Berücksichtige den Zufallszweig richtig

Eine epsilon-gierige Regel exploriert mit Wahrscheinlichkeit $\epsilon$ gleichverteilt und wählt andernfalls eine gierige Aktion. Angenommen, unter vier Aktionen gibt es eine gierige und $\epsilon =\mathrm{0,2}$. Ihre Auswahlwahrscheinlichkeit ist $\mathrm{0,8}+\mathrm{0,2}\mathrm{/}4=\mathrm{0,85}$. Jede andere Aktion hat die Wahrscheinlichkeit 0,05. Der Zufallszweig umfasst auch die gierige Aktion.

Wenig Exploration früh im Training kann nützliche Aktionen ungetestet lassen; viel Exploration spät im Training kostet weiterhin Belohnung. Ein Plan kann im Grenzwert gierig werden und dennoch jedes relevante Paar unendlich oft ausprobieren. Diese GLIE-Eigenschaft ist stärker als das bloße Senken von Epsilon, und die Erreichbarkeit ist dafür entscheidend, ob alle Zustände besucht werden.

Bevorzuge Aktionen mit wenigen Beobachtungen

Eine Explorationsfunktion kann eine Wertschätzung um einen Bonus ergänzen. Wähle bei $f(u,n)=u+k\mathrm{/}n$ für eine ausprobierte Aktion die Aktion mit dem größten Wert. Gib nicht ausprobierten Aktionen Vorrang, etwa den Wert $+\mathrm{\infty }$. Bei $k=10$ erhält ein Wert von 5 nach 20 Versuchen den Wert 5,5; ein Wert von 4 nach zwei Versuchen erhält 9. Die seltener ausprobierte Aktion wird trotz ihrer niedrigeren aktuellen Schätzung gewählt.

Der Bonus kann auch in einen Aktualisierungszielwert eingehen: $r+\gamma {\max }_{a^{\mathrm{\prime }}}f(Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }}),N(s^{\mathrm{\prime }},a^{\mathrm{\prime }}))$. Dadurch wird die Attraktivität unerforschter Aktionen auf frühere Zustände zurückübertragen. Optimistische anfängliche Q-Werte können ebenfalls dazu anregen, Aktionen auszuprobieren, deren Schätzungen noch nicht durch Erfahrung korrigiert wurden.

Nutze eine Konfidenzschranke für Banditen

Ein mehrarmiger Bandit hat einen Entscheidungszustand und mehrere Arme mit unbekannten festen mittleren Belohnungen. Jeder Zug vermittelt dem Agenten etwas über die Belohnungsverteilung eines Arms. UCB1 setzt beschränkte unabhängige Belohnungsziehungen mit einer festen Verteilung pro Arm voraus; skaliere Belohnungen auf den Bereich 0 bis 1. Ziehe jeden Arm einmal und wähle dann den größten Wert

Dabei ist ${\bar{x}}_j$ der Stichprobenmittelwert von Arm $j$, $n_j$ seine Zugzahl und $N$ die Gesamtzahl der Züge über alle Arme. Der Bonus wächst für Arme, die selten ausprobiert wurden. Bei Mittelwerten von 0,6 und 0,5 nach 10 beziehungsweise 2 Zügen gilt $N=12$. Die Werte betragen etwa 1,30 und 2,08, also wird der zweite Arm gewählt. Der Wert kann 1 überschreiten, obwohl beobachtete Belohnungen das nicht können: Er ist ein Entscheidungsindex und keine beobachtete Belohnung.

Miss die Kosten des Lernens

Bedauern vergleicht die gesammelte Belohnung mit dem, was optimale Entscheidungen eingebracht hätten. Bei einem stationären Banditen mit einem tatsächlich schlechteren Arm führt ein festes positives Epsilon dazu, dass dieser Arm weiterhin mit positiver Rate gewählt wird. Dadurch entsteht linear wachsendes erwartetes Bedauern. Unter seinen Annahmen für stochastische Banditen hat UCB1 logarithmisch wachsendes erwartetes Bedauern. Ein sorgfältig abgestimmter Plan mit abnehmendem Epsilon kann ebenfalls diese Größenordnung erreichen; eine beliebige Abnahme kann das nicht garantieren.

Der Off-Policy-Zielwert des Q-Lernens erlaubt explorierende Stichproben, ohne die angestrebten optimalen Werte neu zu definieren. Exploration beeinflusst dennoch die während des Trainings gesammelte Belohnung. Nutze bei physischen Systemen Simulation, aufgezeichnete Erfahrungen oder Beschränkungen erlaubter Aktionen, damit die Exploration keinen Schaden verursacht.

Eine Q-Tabelle speichert eine Zahl für jedes Zustands-Aktions-Paar. Bei einem großen Problem werden viele Paare möglicherweise nie besucht. Getrennte Einträge geben außerdem keine Beobachtungen zwischen ähnlichen Situationen weiter. Approximatives Q-Lernen ersetzt die Tabelle durch eine Funktion von Merkmalen.

Stelle Werte als gewichtete Summe dar

Ein Merkmal $f_i(s,a)$ ist eine Zahl, die einen Aspekt des Zustands und der Aktion beschreibt. Für einen Lieferroboter könnten Merkmale den Akkustand, die Entfernung zu einer Ladestation und wartende Pakete beschreiben. Eine lineare Approximation lautet

Die Gewichte $w_i$ beschreiben, wie stark jedes Merkmal beiträgt. Merkmale können sowohl von der Aktion als auch vom Zustand abhängen, sodass verschiedene Entscheidungen im selben Zustand unterschiedliche Werte haben können.

Aktualisiere jedes Gewicht anhand eines Fehlers

Berechne den aktuellen Q-Wert und dann den Zielwert $y=r+\gamma {\max }_{a^{\mathrm{\prime }}}Q(s^{\mathrm{\prime }},a^{\mathrm{\prime }})$. Die Differenz $\delta =y-Q(s,a)$ bestimmt jede Aktualisierung:

Alle für Zielwert und Fehler verwendeten Werte stammen aus den Gewichten vor der Aktualisierung. Ein Merkmal mit dem Wert null bewirkt keine Änderung seines Gewichts. Ein Merkmal ungleich null skaliert die Anpassung einschließlich ihres Vorzeichens.

Für die Gewichte $(1;-\mathrm{0,5})$ und die aktuellen Merkmale $(1,2)$ lautet die Schätzung $1(1)+(-\mathrm{0,5})(2)=0$. Angenommen, die Belohnung beträgt 4, der beste nächste Q-Wert ist 4 und $\gamma =\mathrm{0,9}$. Der Zielwert ist $4+\mathrm{0,9}(4)=\mathrm{7,6}$, also $\delta =\mathrm{7,6}$. Mit $\alpha =\mathrm{0,1}$:

Die neue Schätzung für dieselben Merkmale beträgt $\mathrm{1,76}+\mathrm{1,02}(2)=\mathrm{3,8}$. Die Aktualisierung geteilter Gewichte ist nicht dasselbe wie das Ersetzen eines unabhängigen Tabelleneintrags durch den Zielwert.

Verstehe Reichweite und Grenzen der gemeinsamen Nutzung

Ein Gewicht wirkt an vielen Vorhersagen mit. Seine Aktualisierung ändert die Werte aller Paare, bei denen das betreffende Merkmal einen Wert ungleich null hat. Das ist Generalisierung und kann dem Agenten helfen, in unbekannten Zuständen sinnvoll zu handeln. Sie kann auch eine fehlerhafte Aktualisierung weitertragen.

Haben zwei Situationen für jede entsprechende Aktion identische Merkmalsvektoren, muss das Modell ihnen identische Aktionswerte geben. Erfordern sie unterschiedliche Aktionen, kann keine Anpassung der Gewichte beide Entscheidungen richtig darstellen. Bessere Merkmale oder eine ausdrucksstärkere Funktion sind nötig. Tabellarisches Lernen ist der Spezialfall mit einem Indikatormerkmal für jedes Zustands-Aktions-Paar, das nur für dieses Paar aktiv ist.

Die Konvergenzgarantie für tabellarisches Q-Lernen gilt nicht für beliebige Funktionsapproximationen. Off-Policy-Bootstrapping mit gemeinsam genutzten Vorhersagen kann schwanken oder divergieren. Bewerte daher die gelernte Strategie in getrennten Versuchen. Tiefe Q-Netze lernen Merkmale aus Eingaben wie den Pixeln eines Spielbildschirms; die Strategiesuche passt dagegen eine Strategie direkt an, um die Gesamtbelohnung zu erhöhen.