Bestärkendes Lernen

Kernidee und Bedeutung

Bestärkendes oder verstärkendes Lernen (englisch reinforcement learning, RL) ist ein Lernstil des maschinellen Lernens. Ein KI-Agent führt selbstständig Aktionen in einer dynamischen Umgebung aus. Die Umgebung meldet deren Auswirkungen als Belohnung (Reward) und neuen Zustand (State) zurück. Durch Versuch und Irrtum erlernt der Agent eine Strategie (Policy), welche die Summe der erhaltenen Belohnungen maximiert.

Das Verfahren muss unmittelbare und langfristige Folgen berücksichtigen: Eine zunächst wenig oder negativ belohnte Aktion kann in einen Zustand führen, von dem aus später eine hohe Belohnung erreichbar ist. Zugleich muss der Agent zwischen Exploration, also dem Erkunden unbekannter Möglichkeiten, und Exploitation, dem Ausnutzen des bereits erworbenen Wissens, abwägen.

Die Umgebung wird gewöhnlich als Markow-Entscheidungsproblem modelliert. Klassische dynamische Programmierung kann ein solches Problem lösen, benötigt aber ein genaues mathematisches Modell und ist bei sehr vielen Zuständen nur begrenzt einsetzbar. Verfahren des bestärkenden Lernens setzen grundsätzlich kein vorher bekanntes Modell voraus und können auch für umfangreiche Zustandsräume verwendet werden. Ein einfacher modellfreier Ansatz ist Q-Lernen, das Erfahrungswerte für Zustände und Aktionen direkt speichert. Bei wenigen Zuständen und Aktionen können dafür Tabellen verwendet werden.

Ein Spezialfall ist Reinforcement Learning through Human Feedback (RLHF): Ein durch menschliche Interaktion und überwachtes Lernen vorprogrammiertes Bewertungsmodell ergänzt die Rückmeldung aus der Umgebung. Einfache Anwendungsbeispiele sind ein Saugroboter, dessen Belohnung die in einer bestimmten Zeit aufgesaugte Staubmenge ist, und ein Roboter, der ein Zielfeld in einem Labyrinth mit möglichst wenigen Schritten erreichen soll.

Mathematisches Modell

Die fünf Grundbegriffe sind Agent, Umwelt, Zustände, Aktionen und Belohnungen. Die Interaktion findet zu diskreten Zeitpunkten t ∈ ℕ₀ statt: Der Agent befindet sich in einem Zustand, wählt eine Aktion und erhält eine reellwertige Belohnung.

Ein Markow-Entscheidungsproblem (Markov Decision Process, MDP) ist das Tupel (S, A, T, r, p₀). Dabei bezeichnet S die Zustandsmenge und A die Aktionsmenge. Das Aktionsmodell beziehungsweise die Transitionswahrscheinlichkeit T: S × A × S → [0,1] beschreibt mit T(sₜ, aₜ, sₜ₊₁) = p(sₜ₊₁ | sₜ, aₜ), wie wahrscheinlich nach Aktion aₜ im Zustand sₜ der Folgezustand sₜ₊₁ ist. Die Belohnungsfunktion r: S × A × S → ℝ ordnet jedem Zustandsübergang eine Belohnung zu. Die Startverteilung p₀: S → ℝ gibt für jeden Zustand an, wie wahrscheinlich der Agent dort beginnt.

Eine Policy π ist eine Kollektion von Wahrscheinlichkeitsmaßen (πₜ(· | s)) für die möglichen Aktionen. πₜ(a | s) gibt die Präferenz beziehungsweise Wahrscheinlichkeit an, mit der der Agent zum Zeitpunkt t im Zustand s die Aktion a auswählt. Als Zufallsvariable wird dies durch Aₜ ∼ πₜ(· | Sₜ) ausgedrückt.

Langfristiger Gewinn und Erkundung

Die Qualität einer Policy lässt sich anhand ihres Gewinns mit der optimalen Policy π* vergleichen. Ziel ist die Maximierung des erwarteten Gesamtgewinns, auch Total Discounted Reward oder kumulierter Reward genannt:

E[Gₜ] = E[Σᵢ₌₀^∞ γⁱ · rₜ₊ᵢ] mit 0 ≤ γ < 1.

Der Diskontierungsfaktor γ gewichtet kurzfristige Belohnungen stärker als spätere und sorgt bei kontinuierlichen Problemen mit unendlich vielen Zustandsübergängen dafür, dass die Summe gegen einen Grenzwert konvergiert. Für γ = 0 zählt ausschließlich die direkte Belohnung; für γ → 1 gewinnen zukünftige Belohnungen immer mehr Gewicht. Typische Werte liegen zwischen 0,95 und 0,99.

Sind alle Bestandteile eines nicht zu großen MDP bekannt, kann die optimale Policy direkt durch dynamische Programmierung berechnet werden. Häufig ist jedoch T unbekannt. Dann erkundet der Agent die Umgebung, um entweder ein Aktionsmodell oder unmittelbar eine gute Policy zu lernen. Kann er nur einen Teil der Zustände beobachten oder sind die Beobachtungen ungenau, liegt formal ein teilweise beobachtbares Markow-Entscheidungsproblem (Partially Observable Markov Decision Process, POMDP) vor. Zusätzlich können die verfügbaren Aktionen eingeschränkt sein.

Rein zufällige Erkundung ist ineffizient. Bei einer ε-greedy Policy wählt der Agent entweder gierig die nach seinem Wissen erfolgversprechendste Aktion oder eine zufällige Aktion. ε ∈ [0,1] ist die Wahrscheinlichkeit für die Zufallswahl. Der Agent soll vorhandenes Wissen nutzen, sich aber nicht zu früh festlegen.

Bestärkendes Lernen besitzt zwei wesentliche Fähigkeiten: Der Agent kann seine Umwelt aktiv erforschen und seine Policy anhand der Rückmeldungen verbessern; außerdem kann er eine optimale Funktion approximieren, wenn ihre direkte Berechnung zu aufwendig ist. Muss die Umwelt erforscht werden, handelt es sich um ein echtes Lernproblem. Ist das Modell vollständig bekannt, aber für eine analytische Lösung zu umfangreich, ist es eigentlich ein Planungsproblem.

Modellfreie Lernverfahren

Lernverfahren werden grob in modellfreie und modellbasierte Methoden eingeteilt. Modellfreie Methoden lernen optimale Handlungen, ohne vorhersagen zu können, in welche Folgezustände diese führen. Sie sind meist wertbasiert oder strategiebasiert; ihre Mischform heißt Actor-Critic.

Wertbasierte Methoden bestimmen für jedes Zustands-Aktions-Paar den kumulierten Reward aus der direkten Belohnung und allen erwarteten zukünftigen Belohnungen. Der Agent lernt eine Nutzenfunktion, die diesen Wert maximiert. Kleine Zustands- und Aktionsräume erlauben Tabellen, die nach jeder Rückmeldung aktualisiert werden. Bei großen Räumen wird die Funktion beispielsweise durch eine Fourierreihe oder ein neuronales Netz approximiert.

Monte-Carlo-Methoden schätzen den Wert einer Aktion, indem sie viele zufällig ausgewählte Episoden ausführen und den Mittelwert der nach der Aktion erhaltenen Belohnungssummen bilden. Eine Episode ist ein vollständiger Ablauf mit einem Ende. Die Aktualisierung erfolgt erst nach ihrem Abschluss, weshalb das Verfahren nur für episodische Aufgaben geeignet ist. Der weitere Verlauf beeinflusst die Bewertung: Ein ungünstiger späterer Verlauf kann den Schätzwert einer zuvor sinnvollen Aktion senken und ohne Gegenmaßnahmen zu einer suboptimalen Lösung führen.

Temporal Difference Learning aktualisiert seine Schätzung dagegen nach jedem Schritt. Es verbindet die unmittelbar gemeldete Belohnung mit einer Schätzung des optimalen zukünftigen Verlaufs. Dadurch ist die Bewertung vom weiteren Episodenverlauf unabhängig, benötigt weniger Zeit und funktioniert auch bei Aufgaben, die unbegrenzt weiterlaufen. Die Konvergenz zur optimalen Wertfunktion wurde bewiesen. Eine verbreitete Variante ist Q-Lernen. Bei kooperierenden Agenten kann dessen Konvergenz bislang nur in trivialen Fällen garantiert werden; Heuristiken liefern dennoch oft praktisch brauchbares Verhalten, weil der ungünstigste Fall selten eintritt.

Strategiebasierte Verfahren maximieren den erwarteten kumulierten Reward direkt, indem sie die Policy parametrisieren. Meist geschieht dies durch stochastische gradientenbasierte Optimierung, den Policy Gradient. Bekannte Verfahren sind REINFORCE, Trust Region Policy Optimization (TRPO) und Proximal Policy Optimization (PPO).

REINFORCE und modellbasierte Verfahren

REINFORCE schätzt den Gradienten des erwarteten Gewinns ∇θ Eτ∼pθ[R₀], um die Parameter θ der differenzierbaren Policy πθ(a | s) anhand empirisch erzeugter Spielabläufe zu aktualisieren. Ein Spielablauf ist τ = (s₀, a₀, s₁, a₁, …, sT, aT). Seine Verteilung hängt sowohl von der Policy als auch von der möglicherweise nichtdeterministischen, vom Agenten nicht beeinflussbaren Umgebung ab:

pθ(τ) = μ(s₀) ∏ₜ₌₀^T p(sₜ₊₁ | sₜ, aₜ) · πθ(aₜ | sₜ),

wobei μ die Verteilung der Startzustände ist. Unter Verwendung der Leibnizregel und der Beziehung ∇x log(f(x)) = ∇x f(x) / f(x) ergibt sich der erwartungstreue Gradientenschätzer

∇̂θ Eτ∼pθ[R₀] = R₀ · Σₜ₌₀^T ∇θ log(πθ(aₜ | sₜ)).

Mit der Lernrate η erfolgt die Aktualisierung durch θₜ₊₁ ← θₜ + η ∇̂θ Eτ∼pθ[R₀].

Modellbasierte Methoden lernen das Aktionsmodell T und die Belohnungsfunktion r oder verwenden ein bekanntes Modell. Der Agent kann damit für beliebige Zustands-Aktions-Paare vorhersagen, was bei einer Aktion geschehen wird, und ist nicht an die Reihenfolge eines tatsächlich erlebten Ablaufs gebunden. Das ermöglicht explizite Planung. MuZero von DeepMind nutzt dies zur Vorausberechnung, die etwa in Schach und Go besonders wichtig ist.

Auf dem Dyna-Algorithmus beruhende Methoden verbinden modellbasierte und modellfreie Ansätze. Das gelernte Modell erzeugt künstliche, auch als halluziniert bezeichnete Daten, mit denen anschließend eine Policy und/oder Wertfunktion trainiert wird. Forschende erhoffen sich außerdem, dass modellbasierte RL-Methoden künftig zum Verständnis realer Kausalitäten in Medizin, Sozial- und Wirtschaftswissenschaften sowie der Politikgestaltung beitragen können; dieser Bereich wird als Causal Machine Learning bezeichnet.