Lernen in Neuronalen Agenten

Begriffliche Grundlagen

Übersicht über wesentliche Aspekte des Lernens

Verhalten

Entspricht dem natürlichsprachlichen Begriff des Verhaltens und umfasst alle strukturierten Interaktionen mit der Umwelt. Dabei kann man, sofern man das möchte, zwischen komplexem Verhalten und Basisverhalten unterscheiden (wobei sich komplexes Verhalten aus Basisverhalten zusammensetzt)

Agent

Ein Agent ist eine physische oder virtuelle Entität (Ferber 2001),

1. die selbständig in einer Umwelt agieren kann
2. die direkt mit anderen Agenten kommunizieren kann
3. die durch eine Menge von Absichten angetrieben wird (in Form von individ. Zielen, Befriedigungs-/Überlebensfunktionen, die sie versucht zu optimieren)
4. die eigene Ressourcen besitzt
5. die fähig ist, ihre Umwelt wahrzunehmen (nur in einem best. Ausmaß!)
6. die nur eine partielle Repräsentation der Umwelt (Modell) besitzt
7. die bestimmte Fähigkeiten besitzt (oder erwirbt) und Dienste offerieren kann
8. die sich ggf. selbst reproduzieren kann
9. deren Verhalten darauf ausgerichtet ist, ihre Ziele unter Berücksichtigung der ihr zur Verfügung stehenden Ressourcen und Fähigkeiten zu befriedigen und die dabei auf ihre Wahrnehmung, ihre internen Modelle und ihre Kommunikation mit anderen Agenten (oder Menschen) angewiesen ist

Lernprozesse

• Zweck der Informationsverarbeitung: situationsgerechtes Verhalten in der Umwelt
• Zwecke des Lernens: Veränderung des Verhaltens und damit Vergrößerung des Einsatzbereichs in dem Agent eingesetzt werden kann
• Realisierung des Lernprozesses: Umstrukturierung der Steuerarchitektur

Perception-Action-Cycle

• Wahrnehmungs-Handlungs-Zyklus
• Lernen erfordert eine sensorische Beobachtung der Umwelt und eine Aufgabe bzw. zielgerichtete Handlung, deren Erfolg/Misserfolg für den Agenten erkennbar sein muss
• Resultat: Selbstoptimierung des Verhaltens (um bestmöglich die gestellte Aufgabe zu erfüllen)

Stability-Plasticity Dilemma

Ist das Problem auf neue Situationen reagieren zu können und diese zu lernen, dabei aber bereits angesammeltes Wissen zu bewahren.

Exploration-Exploitation Dilemma

Ebenfalls ein Standardproblem von lernenden Systemen. Um neues Wissen über meine Umwelt zu erlangen müsste ich ständig explorieren, andererseits sollte ich aber auch ständig bekannte Aktionen ausführen um bereits gelerntes Wissen anzuwenden (exploitation) Lösungsansätze kommen später

Ebenen des Lernens und der Wissensrepräsentation

prozedurales Wissen:

• Verhaltenswissen bzw. Sensomotorische Intelligenz
• Beschreibt für eine ganz konkrete sensorische Situation die möglichen Aktionen des Agenten
• "Gewusst WIE"

deklaratives Wissen:

• deliberatives oder auch kognitives Wissen
• stellt Repräsentation der Umwelt dar
• dient der Planung von Verhalten
• "Gewusst WAS"

Aus deklarativem Wissen können Subziele einer Handlungsstrategie festgelegt werden, welche dann mit Hilfe des prozeduralen Wissens abgearbeitet werden. Zum Beispiel könnte ein, mittels deklarativem Wissen erstelltes Subziel, auf dem Weg ein Wasserglas zu greifen, sein, den Arm auszustrecken. Das prozedurale Wissen beschreibt dann wie die Muskeln anzusteuern sind, um den Arm nach vorne zu bekommen.

Vergleich:

Konditionierungslernen

• ein grundlegendes Lernprinzip im Perception-Action-Cycle

klassische Konditionierung

• ein unkonditionierter Stimulus (US) erzeugt immer eine sichtbare Reaktion (UR) und ist angeboren, wie ein Reflex
  • z.B Nahrung -> Speichelfluss
• ein konditionierter Stimulus (CS) erzeugt zunächst keine sichtbare Reaktion (CR)
  • z.B. Glockenschlag
• durch die kombinierte Anwendung von US und CS ist es möglich, ein CR auszubilden, welches dem UR ähnelt bzw. mit ihm identisch ist
• Folge: durch die alleinige Anwendung des CS kommt es zur sichtbaren Reaktion UR
  • z.B. Die Fütterung eines Hundes (US) löst bei diesem zunächst Speichelfluss (UR) aus. Ertönt bei jeder Futtergabe ein Glockenschlag (CS) führt dies dazu, dass nach einiger Zeit der Glockenschlag allein ausreicht um den Speichelfluss zu aktivieren. (CR=UR)

-> Detektion von Beziehungen zwischen Ereignissen in der Umwelt

instrumentale Konditionierung

• Aktionen die in bestimmten Situationen zu Befriedigung führen werden häufiger ausgeführt als solche die zu Unzufriedenheit führen, d.h. unmittelbar auf eine Handlung folgt eine Konsequenz
• die Handlung fungiert somit als Instrument für die Konsequenz
  • z.B. eine Ratte die eine Taste berührt und daraufhin Futter bekommt, wird dies wiederholt tun, wohingegen sie es vermeiden wird die Taste zu berühren, wenn sie daraufhin einen Stromschlag bekommt

-> Detektion von Beziehungen zwischen Verhalten und nachfolgendem Ereignis in der Umwelt

Reinforcement Learning

Grundidee des RL

Für jede ausgeführte Handlung (oder auch am Ende eines Handlungsstranges) erhält ein Agent eine Belohnung oder Bestrafung (Reinforcement). Diese akkumuliert sich über die Zeit. Ziel des Reinforcementlearnings ist es nun, durch Lernen solche Entscheidungsstrategien zu finden, so dass die akkumulierten Reinforcements optimal werden.

Charakterisierung des RL

• Lernparadigma:
  • irgendwo zwischen überwachtem Lernen und unüberwachtem Lernen
  • nutzt ebenfalls ein Feedback, aber nur zur Bewertung des Verhaltens
    • alleinige Aussage, ob das Verhalten gut war oder schlecht, aber nicht, wie es hätte sein müssen
• Grundsatz (noch mal in einem Satz):
  • autonomes Lernen komplexer Wahrnehmungs-Verhaltens-Muster basierend auf einem unspezifischen skalaren Signal, welches das Systemverhalten bewertet
• Findet Anwendung in: Robotik, Optimaler Regelung, Spielen uvm.

General RL-Task

<graphviz> digraph G { Umgebung -> Agent [label="Zustand (State)"]; Umgebung -> Agent [style=dotted,label="Reinforcement"]; Agent -> Umgebung [label="Aktion"]; } </graphviz>

• Ziel: lernen die Aktionen auszuführen, die zum größten Langzeit-Reward führen
• $R_{t}=\sum _{k=0}^{\infty }\gamma ^{k}\cdot r_{t+k+1}$
  • $R_{t}$ ... Langzeitreward
  • $\gamma$ ... Discountfaktor [0,1] ... schwächt den Einfluss ferner Rewards ab
  • $r_{t}$ ... reward zum Zeitpunkt t
• Durchführung: Ausführung einer Aktion und beobachten des Ergebnisses
  • Anpassen der Policy, welche die Aktion ausgewählt hat, je nach dem ob das Reward positiv oder negativ ausgefallen ist, damit die Aktion öfter ausgeführt wird oder weniger oft, wenn der selbe Zustand wieder erreicht werden sollte.
• Die beste Aktion in einem Zeitschritt führt nicht immer zum besten Langzeitergebnis!

schwache und starke RL-Verfahren

schwache RL-Verfahren

• Haben nur eine begrenzte zeitliche Sicht
• suchen nur eine lokal optimale Policy
• $\gamma \rightarrow 0$
• Wählen immer die für ihre Sicht optimale Aktion aus
• z.B. Räuberschach

starke RL-Verfahren

• besitzen zeitlich unbegrenzte Sicht
• Versuchen eine global optimale Policy zu erlernen
• $\gamma \rightarrow 1$
• Maximierung der Summe aller Rewards
• z.B. Schach, Backgammon

RL als MDP

• MDP (Makrov Decision Processes)
• Annahmen
  • es gibt nur eine endliche Menge an Zuständen
  • es gibt eine endliche Menge an ausführbaren Aktionen
  • Der Zustand kann zu jeden Zeitpunkt beobachtet werden und es ist möglich eine Aktion auszuwählen für den Zustand anhand einer Policy
  • Nach der Ausführung der Aktion gibt es ein reward
  • Der Zustand wird durch die Aktion in den nächsten Zustand überführt
• Markov Annahme
  • Der nächste Zustand wird ausschließlich durch den aktuellen Zustand und die auszuführende Aktion bestimmt
• Damit kann der zu erwartende Reward anhand des aktuellen Zustandes berechnet werden

Basiskomponenten eines RL-Agenten

Policy

• Entscheidungsfunktion die angibt welche Aktion ausgeführt werden soll wenn sich der Agent in einem bestimmten Zustand befindet
• Die Policy bestimmt das Verhalten und die Performance des Agenten alleine
• Alle anderen Komponenten existieren nur damit die Policy verbessert und angepasst werden kann

Reinforcement Funktion

• Definiert die Ziele des Agenten
• Wird vom Entwickler vorgegeben
• Ist eine Funktion die den Zustand bewertet und angibt wie erwünscht er ist -> definiert was gut und was schlecht ist
• Darf während des Lernens nicht geändert werden, sonst kann man keine Policy erreichen
• Das Reward sagt dem Agenten WAS erreicht werden soll, aber nicht WIE

Value/Action Funktion

• Value V(s) ist eine Funktion welche angibt welchen Reward man erhalten würde wenn man sich im Zustand S befindet und der Policy folgt
  • $V^{\pi }(s)=E_{\pi }\lbrace R_{t}\mid s_{t}=s\rbrace$
• Action-Value Q(s,a) ist eine Funktion, die angibt welchen Reward man erhalten würde, wenn man sich im Zustand S befindet, die Aktion a ausführt und dann der Policy folgt
  • $Q^{\pi }(s,a)=E_{\pi }\lbrace R_{t}\mid s_{t}=s,a_{t}=a\rbrace$

• Reinforcements bestimmen, wie erwünscht der aktuelle Zustand ist
  • sie werden direkt aus der Umgebung bezogen
• Values hingegen geben die Langzeit-Erwünschtheit an, nachdem die am wahrscheinlichsten erreichten Zustände mit ihren jeweiligen Reinforcements errechnet wurden
  • sie sind nur Schätzungen aus der Beobachtungsfolge, welche ein Agent über die gesamte Zeit macht
  • somit kann nicht nur kurzsichtig agiert werden sondern auch langfristig
  • kann approximiert werden durch Lookup Tabellen oder MLP/RBF-Netzwerke

• Eine der Hauptaufgaben des RL ist es, die Value-Funktion durch Lernen effizient zu approximieren

Umgebungsmodell

• immitiert das Verhalten der Umgebung
• kann durch den Entwickler vorgegeben werden oder selbst erlernt werden
• hilft den neuen Zustand vorherzusagen wenn man eine bestimmte Aktion ausführt
• nicht jeder RL-Agent besitzt ein Umgebungsmodell, aber es erhöt die Geschwindigkeit mit der ein Agent die optimale Policy lernt
• modellfreie RL-Agenten finden die selbe Lösung, es dauert nur länger

Umgebung

• muss wenigstens teilweise beobachtbar sein
• Umgebung gibt die möglichen Aktionen mit vor

State (Zustand):

• Alle notwendigen Parameter der Umgebung, die die Entscheidung beeinflussen eine Aktion auszuwählen, sind dem Agenten zugänglich
• wie z.B. globale Positionsinformation

Situation:

• Der Agent hat nur Zugriff auf einen Teil der Parameter, so dass der aktuelle Zustand nicht immer eindeutig beschrieben werden kann
• z.B. Navigation mit IR oder Ultraschall Sensoren

Schätzung des States:

1. Zusätzliche Sensoreinflüsse nutzen
2. Weg ab Startpunkt merken
3. Aus mehreren Umgebungsbeobachtungen und einem Umgebungsmodell State schätzen

Optimale Policies finden

Policy Iteration

• hier wird die optimale Policy gesucht, indem verschiedene Strategien direkt miteinander verglichen und bewertet werden

Value/Action-Value Iteration

• indirekte Suche nach der besten Policy durch die Value-Funktion
• dazu wird für jeden Zustand (oder jedes Zustands-Aktions-Paar) die Value-Funktion berechnet und das Maximum als beste Policy festgelegt
• bei komplexen Umgebungen führt dies aber schnell zu einem sehr großen Rechenaufwand und Speicherbedarf

Value/Action-Value Iteration

Das Bellman'sche Optimalitätsprinzip

• Der Teilplan eines optimalen Plans ist ebenfalls optimal!
• Eine optimale Policy hat die Eigenschaft, dass für einen beliebigen Zustand und beliebige Aktionen alle nachfolgenden Entscheidungen wieder eine optimale Policy generieren -> Gebirgswanderung

Die Bellman'sche Gleichung

• Values sind Funktionen des Zustandes oder der Zustands-Aktions-Paare und schätzen wie gut es für einen Agenten ist, sich in diesem Zustand zu befinden oder diese Zustands-Aktions-Auswahl zu treffen (unter Berücksichtigung einer speziellen Policy)
• $V^{\pi }(s_{t})=E\lbrace r_{t+1}+\gamma \cdot V^{\pi }(s_{t+1})\rbrace$
• $Q^{\pi }(s_{t},a_{t})=E\lbrace r_{t+1}+\gamma \cdot Q^{\pi }(s_{t+1},a_{t+1})\rbrace$

Optimale Value-Funktionen

• Optimale Policies haben alle eine optimale Zustands-Value-Funktion $V^{\ast }(s)$ bzw. Zustands-Aktions-Value-Funktion $Q^{\ast }(s,a)$ gemeinsam
• Idee (1): Der Zustands-Value, unter Berücksichtigung einer optimalen Policy, muss dem Erwartungswert für die beste Aktion ausgehend von diesem Zustand, unter Berücksichtigung der optimalen Policy, sein
  • $V^{\ast }(s){\stackrel {!}{=}}{\underset {a\in A(s)}{\mathrm {max} }}\left[Q^{\pi ^{\ast }}(s,a)\right]={\underset {a}{\mathrm {max} }}\left[E\lbrace r_{t+1}+\gamma \cdot V^{\ast }(s_{t+1})\mid s_{t}=s,a_{t}=a\rbrace \right]$
• Idee (2): Der Aktions-Value eines Zustands-Aktions-Paares, unter Berücksichtigung einer optimalen Policy, muss dem Erwartungswert der besten Aktion des darauffolgenden Zustandes, unter Berücksichtigung der optimalen Policy, sein
  • $Q^{\ast }(s,a){\stackrel {!}{=}}{\underset {a_{t+1}\in A(s_{t+1})}{\mathrm {max} }}\left[Q^{\pi ^{\ast }}(s,a)\right]=E\lbrace r_{t+1}+\gamma \cdot {\underset {a'}{\mathrm {max} }}\left[Q^{\ast }(s_{t+1},a')\right]\mid s_{t}=s,a_{t}=a\rbrace$
  • dies bildet die Vorraussetzung für Q-Learning

• Fazit: Wählt man immer die Aktion mit dem größten Aktions-Value, so sollte sich auch der long term Reward maximieren

Q-Learning

• Idee: Bellman'sche Gleichung in eine Updateregel umwandeln, indem zwei aufeinanderfolgende Zeitschritte betrachtet werden
  • Policy Bewertung: Value-Funktion lernen
  • Policy Verbesserung: Maximum-Suche bezüglich der gelernten Value-Funktion
  • erneute Wiederholung führt zur optimalen Value-Funktion

Q-Learning-Algorithmus:

• Initialisierung aller geschätzten ${\hat {Q}}(s,a)$ mit 0 [Anm.: Bei unendlich häufiger Ausführung des Algorithmus nähern sich die geschätzen ${\hat {Q}}$ den optimalen (welche den Long-Term Reward maximieren) $Q^{\ast }$ an.]
• beobachte den aktuellen State $s=s_{t}$
• Wiederhole:
  • Wähle eine Aktion $a=a_{t}$ im aktuellen Zustand entsprechend der Policy (z.B. greedy Auswahl der Aktionen mit maximalem Q-Wert oder Bolzmann Auswahl) und führe sie aus
  • Erhalte den sofortigen reward
  • Beobachte den neuen Zustand $s'=s_{t+1}$
  • Update des geschätzten ${\hat {Q}}$ nach folgender Update-Gleichung:
    ${\hat {Q}}_{k+1}(s,a):={\hat {Q}}_{k}(s,a)+\beta \cdot \left(r+\gamma \cdot \max _{a'\in A}\left({\hat {Q}}_{k}(s',a')\right)-{\hat {Q}}_{k}(s,a)\right)$
  • $s\leftarrow s'$ (s' zu neuem aktuellen Zustand machen)
• bis die Zustände erschöpfend durchsucht wurden, d.h. bis ${\hat {Q}}$ gegen $Q^{\ast }$ konvergiert

Die Updateregel ist wie folgt zu interpretieren:

Die neue Schätzung des Q-Values einer Aktion a (welche soeben durchgeführt wurde) im vorigen Zustand s (Der Zustand vor dem Ausführen der Aktion a) setzt sich aus der alten Schätzung dieses Wertes zusammen plus einen Anpassungsterm, welcher mit einer skalaren Größe $\beta$ gewichtet ist, welche die Lerngeschwindigkeit beeinflusst. Der Anpassungsterm ist der, durch Ausführung von a, erhaltene Reward + dem maximal möglichen Q-Value des Zustandes in dem ich mich aktuell befinde, minus dem Q-Value des vorigen Zustandes. Der Faktor $\gamma$ sorgt dafür, dass die Q-Werte mit steigender Entfernung (im Sinne von aufeinander folgenden Zuständen) zu einem Zustand, in welchem es einen großen Reward gibt, stetig fallen. Damit kann eine Art Q-Value Gradientenaufstieg in Richtung von besonders positiven Zuständen erfolgen (oder eben eine Abwendung von besonders Negativen). Die Subtraktion des Q-Values am Ende sorgt nur dafür, dass diese nicht ins Endlose steigen. Sieht man gut, wenn man $\beta =1$ annimmt.

Möglichkeiten zur Repräsentation der geschätzten Q-Funktion:

• Tabellierte State-Action-Paare
  • exponentiell wachsender Speicherbedarf
• neuronale Funktionsapproximatoren
  • adaptive Vektorquantisierung
  • "supervised" Learning
  • brauche für jede Aktion einen Funktionsapproximator

Exploration/Exploitation revisited

Wie schon mal angesprochen sollte man nicht immer nur exploren aber auch nicht nur exploiten

Zwei Verfahren besprochen, das Dilemma "schön" zu lösen:

Epsilon-Greedy:

• mit Wahrscheinlichkeit $1-\epsilon$ wird die Aktion ausgewählt, welche den höchsten Reward verspricht (welcher der höchste Q-Wert anhängt)
• mit Wahrscheinlichkeit $\epsilon$ wird eine zufällige Aktion ausgewählt

Boltzmann-Aktionsauswahl:

• $P(a_{i})={\frac {\mathrm {e} ^{\left({\frac {{\hat {Q}}(s,a_{i})}{T(t)}}\right)}}{\sum _{j=1}^{M}\mathrm {e} ^{\left({\frac {{\hat {Q}}(s,a_{j})}{T(t)}}\right)}}}$
• Boltzmann Temperatur $T(t)$ bestimmt den Grad der Zufälligkeit der Aktionsauswahl
• für $T\rightarrow \infty$ ist die Auswahl unabhängig vom Q-Wert ($P(a_{i})=1/M$ mit M - Anzahl der möglichen Aktionen)
  • entspricht einem ausgeprägten Entdeckungsverhalten
• für $T\rightarrow 0$ werden Aktionen mit hohem Q-Wert ausgewählt und Aktionen mit kleinem Q-Wert vernachlässigt
  • keinerlei Entdeckungsverhalten
• Mittelweg: $T(t)={\frac {T_{start}}{1+\alpha \cdot t}}$
  • es werden gelegentlich Aktionen ausgeführt, die nicht der Policy entsprechen

SARSA-Learning

• ähnlich dem Q-Learning
• Unterschied: nehme den Q-Wert des Weges, den ich gegangen bin (Q-Learning nimmt den maximalen Q-Wert zum lernen)
• State -> Action -> Reinforcement -> State -> Action
• Die Update Regel der Q Werte lautet:
  $Q_{k+1}(s,a):=(1-\beta )\cdot Q_{k}(s,a)+\beta (r+\gamma \cdot Q_{k}(s',a'))$
• mit einer Greedy-Policy konvergiert dieses Verfahren gegen das Q-Learning

On-Policy und Off-Policy

On-Policy:

• Policy, welche die Aktionsauswahl steuert, ist identisch mit der Policy, mit der gelernt werden soll
• typischer Vertreter: SARSA-Learning

Off-Policy:

• Policy, welche die Aktionsauswahl steuert, muss nicht identisch mit der Policy sein, mit der gelernt werden soll
• typischer Vertreter: Q-Learning (z.B. Stochastische Policy für Aktionsauswahl, Greedy-Policy zum Lernen)
• Vorteil: Lern-Policy kann "gierig" sein, wärend die Policy für die Aktionsauswahl die Möglichkeit hat, alle möglichen Aktionen auszuprobieren

Eligibility Traces

Grundidee

• Ziel: Rückverteilung der temporealen Differenz von $\Delta V$ bzw. $\Delta Q$ auf alle Zustände bzw. Zustands-Aktionspaare die zu der aktuellen Situation beigetragen haben
• Einsatz: Vor allem bei Delayed RL-Problemen (Zielanfahrten, Spiele)
• erhöhen die Lerngeschwindigkeit des RL-Verfahrens da alle durchlaufenen Zustände und Aktionen aktualisiert werden
• Die Updateregeln ändern sich zu:

$Q(s,a):=Q(s,a)+\beta \cdot \underbrace {\left(r+\gamma \cdot \max _{a'\in A}\left(Q(s',a')\right)-Q(s,a)\right)} _{\Delta Q}\cdot e(s,a)$

$V(s):=V(s)+\beta \underbrace {(r+\gamma \cdot V(s')-V(s))} _{\Delta V}\cdot e(s)$

Realisierungen des Traces

• erfordert geeignete Markierung aller durchlaufenen V- und Q-Values

Accumulating Trace:
$e_{t}(s,a)=\left\{{\begin{matrix}\gamma \cdot \lambda \cdot e_{t-1}(s,a)&{\mathit {wenn}}\ s\neq s_{t}\\\gamma \cdot \lambda \cdot e_{t-1}(s,a)+1&{\mathit {wenn}}\ s=s_{t}\end{matrix}}\right.$

• berücksichtigt Häufigkeit und Aktualität des Zustandes bzw. Zustands-Aktions-Paars
• Diese Version kann instabil werden da Werte >1 möglich sind

Replacing Trace:
$e_{t}(s)=\left\{{\begin{matrix}\gamma \cdot \lambda \cdot e_{t-1}(s)&{\mathit {wenn}}\ s\neq s_{t}\\1&{\mathit {wenn}}\ s=s_{t}\end{matrix}}\right.$

• berücksichtigt nur Aktualität des Zustandes bzw. Zustands-Aktions-Paars (wird dadurch schneller und robuster)

Einfluss von $\lambda$:

• $\lambda =0$ → TD(0): Alle Traces sind deaktiviert -> Normales TD Lernen
• $0<\lambda <1$: Normale abklingende Traces
• $\lambda =1$: Abklingen des Traces wird nur noch durch $\gamma$ hervorgerufen

Besonderheiten:

• Bei der Ausführung von Off-Policy Aktionen muss der Trace deaktiviert werden, da der Zustand durch Befolgen einer anderen Policy erreicht wurde

Typische Probleme beim RL

POMDPs

• Partially Observable Markov Decision Process
• wird benötigt wenn Umgebung nur teilweise beobachtbar ist
• Lösungsansätze:
  • Ignorieren und hoffen
  • Hinzunahme von weiteren Beobachtungen (Geschwindigkeit, Beschleunigung)
  • Benutzung impliziter interner Zeitinformationen (durch Traces)
  • Hinzunahme fester/variabler Zeitfenster (zur Bewahrung der Sensorinformationen)
  • Karte bauen (sollte aber eigentlich vermieden werden)

Komplexitätsproblem

• Lange Traninigszeiten der Agenten, selbst bei einfachen Aufgaben
• Ursache: Komplexität des Algo's
  • hängt exponentiell von der Größe des Eingangsraumes und der Anzahl der auszuführenden Aktionen entsprechend der optimalen Policy ab
• Komplexität wird maximal bei delayed RL (Reinforcement erst nach Erreichen des Ziels) oder tabula rasa RL (Values mit 0 initialisiert)
• Lösungsansätze:
  • Agent erhält für jede Aktion ein Reinforcement
  • Value-Funktionen optimischtisch realisieren (etwas über dem maximal möglichen Return)
  • angemessene Explorationsstrategien
  • Änderung der Value-Funktion nach jeder Aktion (nicht erst nach Erreichen des Ziels)
  • Eingangsraum zunächst eng um Zielzustand begrenzen und dann immer mehr erweitern
  • Anlernen durch externen Experten (Experte agiert zunächst als Policy)

Neuronale Umsetzung von RL-Agenten

• State- und Action- Space ist immer reichlich groß -> effizienter die Funktion mittels neuronaler Verfahren zu approximieren
• Mapping vom State auf eine Action wird gelernt
• Zwei prinzipielle Ansätze:

1. Partitionierung des Eingangsraumes mittels Vektorquanitsierern (self organizing feature maps, (growing) neural gas), dann wird mittels Q-Tabular - Learning weitergearbeitet
   • Auch benachbarte Neuronen können mitlernen (hat Vor- und Nachteile!)
2. alleiniger Einsatz von Funktionsapproximatoren (Multilayerperceptrons, Radiale Basisfunktionsnetze, Regressionsnetze...)

prinzipieller Aufbau

State Map:

• empfängt Sensorwerte aus dem kontinuierlichen Input Space (IS) und wandelt sie mittels Vektorquanitisierer in einen diskreten State Space um
• jede Parzelle repräsentiert dann einen State, oder eine Stategruppierung

Motor Map:

• kodiert alle möglichen Aktionen des aktuell möglichen State in Form von einfachen Elementaraktionen (z.B. geradeausfahren, rechtsrum...)
• Hier sollte dann theoretisch auch irgendwie ein neuronaler Funktionsapproximator seine Arbeit verrichten. Dazu steht aber im Script nix gescheites.
  • Eine Möglichkeit wäre, dass er das Mapping von den Partitionen der State Map auf eine Aktion der Motor Map macht.
  • Dann gäbe es aber nur eine Motormap, in der ALLE überhaupt möglichen Aktionen stehen
  • Eine andere Möglichkeit, welche so auch im Script angedeutet ist, ist, dass es pro Parzelle der State Map einen Funktionsapproximator gibt, welcher dann... ich hab keine Ahnung was macht - zumal im Abschnitt Q-Learning Algorithm auch kein NN vorkommt

Neuronale Value Approximation am Beispiel TD-Gammons

• nutzt TD-Lernen, daher der Name
• MLP oder RBF-Netz, mit einer oder mehreren Hidden-Schichten
• Input: speziell kodierte Brettsituation
• Output: erwarteter Value für jede angelegte Brettsituation
• Vorgehen:
  • Vor dem Spiel: Netz lernt den Wert einer jeden Situation
  • Während des Spiels: Netz bekommt alle möglichen Züge mittels Zuggenerator präsentiert und gibt geschätzten Wert dieser Züge zurück -> bester Zug ausgewählt
  • Nach dem Spiel: Flasche Sekt aus dem Kühlschrank holen und sich seines Sieges freuen

Inputcodierung:

• 198 Neuronen:
  • 192 Neuronen für die Brettkonfiguration
    • 24 Punkte * 2 Farben * 4 Neuronen für die Anzahl an Steinen auf dem Punkt
    • Anzahl aktivierter Neuronen pro Punkt entspricht bis 3 der Anzahl an Steinen auf diesem Punkt - 4 aktivierte Neuronen heißt 4 oder mehr Steine auf diesem Punkt
  • 2 Neuronen für die Barkonfiguration - Aktivierung von 1/2 je Stein und Farbe
  • 2 Neuronen für die im Aus befindlichen Steine - Aktivierung von 1/15 je Stein und Farbe
  • 2 Neuronen für aktiven Spieler

Outputcodierung:

• ursprünglich 1 Neuron -> Siegwahrscheinlichkeit/Value/Bewertung der Brettsituation
  • später 4 Neuronen
    • 1 Neuron für einfachen Sieg
    • 1 Neuron für zweifachen Sieg
    • 1 Neuron für weiß gewinnt
    • 1 Neuron für schwarz gewinnt

Zuggenerator:

• Rekursive Generierung aller gültigen Folgezüge
• damit Züge bei verschiedenen Würfelaugen nicht vergessen werden: erneuter Durchlauf mit vertauschter Augenzahl
• so entstehen 20-60 gültige Züge pro Würfelkombination

Aktivitätsausbreitung und Lernen:

• Outputaktivität der Hidden-Neuronen:

$y_{i}={\frac {1}{1+e^{-\sum _{j}w_{ij}\cdot x_{j}}}}$

• TD-Lernalgorithmus:

${\underline {w}}_{t+1}={\underline {w}}_{t}+\beta \left(r_{t+1}+\gamma V(t+1)-V(t)\right){\underline {e}}_{t}$

• Update der eligibility-Traces:

${\underline {e}}_{t}=\gamma \cdot \lambda \cdot {\underline {e}}_{t-1}+\nabla _{{\underline {w}}_{t}}\cdot V(s_{t})$ wobei
$\nabla _{{\underline {w}}_{t}}V(s_{t})$... Beitrag des Gewichtes w zu V

• Gewichtsinitialisierung zufällig (damit ist kein Regelwissen initial vorhanden)
• gelernt wird alternierend beidseitig (das Netz spielt gegen sich selbst abwechselnd als schwarzer und weißer Spieler)

Learning Classifier Systems

• LCS kommen aus der symbolischen KI
• sind dadurch entstanden das Expertensysteme mit Genetischen Algortihmen verbunden wurden, um Regeln schneller zu erlernen

Hauptkomponenten

Ein Regel und Nachrichten System:

• regelt die Interaktion mit der Umgebung
• übersetzt die reellen Zahlen der Umgebung in abstrakte Nachrichten
• repräsentiert die aktuelle Policy, welche in Form von Klassifizierern vorliegt, und nimmt die Aktionsauswahl vor

Ein Credit Aufteilungssystem (zum Bewerten der Wissensbasis):

• verteilt die eingehenden Rewards auf alle Regeln
• realisiert die Lern-Policy (durch RL oder "Eimerketten"-Algos)

Ein System zum entwickeln von Klassifizierern:

• Aufgabe ist das explorieren und spezialisieren der Zustand-Aktionsraum Repräsentation

weitere Komponenten

Detektoren:

• erkennen Features in komplexen reellwertigen Eingaben von der Umgebung
• übersetzen diese Eingaben in Nachrichten aus einem Vektor {1,0}

Classifier:

• jeder Classifier beschreibt eine Regel
• jede Regel besteht aus:
  • einer Menge von Bedingungen (Vektor von {0,1,#} # ... Joker)
  • einer Aktion codiert als Vektor von {0,1}
  • einer Stärke, die angibt wie sinnvoll eine Regel ist

Effectors:

• übersetzen Nachrichten in Aktionen die ausgeführt werden sollen

Vorgehen

Aktionsauswahl:

• alle Nachrichten der Umgebung werden gegen alle Classifier-Bedingungen geprüft
• auf einen Zustand können mehrere Regeln zutreffen
• alle Classifier auf die eine Nachricht zutrifft nehmen an einer Auktion teil
• jeder passende Classifier muss dafür ein Gebot abgeben, das sich nach seiner Stärker und seiner Spezifizität richtet (je mehr Joker eine Bedingung enthält desto unspezifischer ist sie)
  • $B_{i}(t)=k\cdot S_{i}(t)\cdot f(specificity)$
  • k ... Risikofaktor
  • $S_{i}(t)$ ... Stärke
• auf jedes Gebot wird ein Rauschen addiert und anschließend das Maximum ausgewählt

Creditverteilung:

• alle Clasifier müssen ihr Gebot bezahlen
  $S_{i}(t+1)=S_{i}(t)-B_{i}(t)\cdot Tax_{bid}$
• jeder Classifier muss eine Kopfsteuer zahlen (vernichtet unsinnige Bedingungen)
  $S_{i}(t+1)=S_{i}(t)-S_{i}(t)\cdot Tax_{life}$
• der gewinnende Classifier muss sein Gebot bezahlen und bekommt das Reward sowie einen Anteil des folgenden Gebotes

$S_{i}(t+1)=S_{i}(t)+R_{i}(t+1)-B_{i}(t)+\gamma \cdot B_{j}(t+1)$

Anpassung der Classifier:

• Deterministisch
  • wenn kein Classifier auf die Nachricht passt wird einfach ein neuer angelegt mit einer zufälligen Aktion
  • die Stärke, der zufälligen Aktion, wird auf den Durchschnitt aller bereits vorhandenen Regeln gesetzt
• Genetischer Algorithmus
  • die stärksten Classifier werden ausgewählt
  • werden gemischt (Übernehmen von Teilen aus dem einen und dem anderen CLassifier um einen neuen zu erstellen)
  • werden mutiert (einzelne Werte werden zufällig geändert)

Multiagenten Systeme

Motivation:

• Lösung komplexer Gesamtaufgaben in Teilaufgaben, die von einzelnen Agenten bearbeitet werden
• Koordination des Zugriffs von mehreren Agenten auf gleiche Ressourcen

Eigenschaften:

• Robustheit
• Parallelisierbarkeit, Skalierbarkeit
• Emergenz (Auftreten neuer Qualitäten)

Wesentliche Arten von Agenten

• Reaktiv: feste Abbildung von Sensoren auf Aktoren
• Operand: Verfügen über innere Zustände und können Wissen über folgen speichern
• Planend / Deliberativ: verfügen über Umweldmodell und wägen Folgen ihrer Handlung ab
• Hybride: Kombinieren Reaktives und deliberatives Verhalten
• Kognitive: Verfügen über komplexe Situationsbeschreibungen und können somit zwischen verschiedenen Zielen abwägen

Arten von Multi-Agenten Systemen

• Koordinierung mehrerer physischer Agenten (Rudel/Schwärme)
• Koordinierung mehrerer Agenten in einem Körper

MAS vs. Monolith

MAS

• Lösung der Gesamtaufgabe durch separate Agenten für Teilaufgaben
• Zerlegung in Teilaufgaben und Festlegung der Spezifik durch Designer oder automatisch möglich
• geeignete Koordinierung der Agenten beim Zugriff auf Ressourcen

Problemdekomposition:

• durch Designer:
  • Definition von Agenten mit Teilaufgaben
  • Festlegung sensorischer Inputs und der Aktionen mit ihren Rewards
  • Festlegung aufgabenspezifischer Netze
• selbstorganisiert duch Agenten:
  • Gegenstand der aktuellen Grundlagenforschung
  • Festlegung von Kriterien zur Generierung neuer Agenten
  • Mechanismen zur Bestimmung geeigneter Inputs und Aktionen mit ihren Rewards

Vorteile:

• bessere Teilperformanz, skalierbar, beherrschbar
• einfache Agenten
• einfache Erweiterbarkeit

Nachteile

• Festlegung der Agenten
• geeignete Zerlegung des Problems muss gefunden werden
• geeignete Koordination der Agenten
• Reward-Dekomposition notwendig

Monolith

• Lösung der Gesamtaufgabe in einer einzigen Struktur
• Verknüpfung aller notwendigen sensorischen Inputquellen
• Ansteuerung der gesamten Aktuatorik
• Erwerb einer einzigen Abbildung vom gesamten sensorischen Input auf die Aktuatorik

Vorteile:

• optimale Performanz
• notwendige Abbildung zwischen Sensoren und Aktoren wird selbst gefunden
• Teilaspekte und Koordinierung können durch Designer gewichtet werden

Nachteile:

• kompliziertes Design und Verteilen des Rewards
• kombinatorische Explosion des Zustandsraumes
• schlechte Erweiterbarkeit

"Mr. Smith, wo sind sie?" oder auch "Koordinierung der Agenten"

Grundarten:

• Wettbewerb
• Kooperation
• Kombination von Kooperation und Wettbewerb

Zentrale Kontrollstrategie

• Agenten haben kein Wissen über die Ziele der anderen Agenten
• nur eine zentrale Struktur besitzt Wissen über die Agenten (a.k.a. "M")
• Agenten liefern Aktionsvorschläge
• Zentrale Struktur realisiert die Auswahl der resultierenden Aktionen

Verteilte Kontrollstrategie

• Agenten haben Wissen über gegenseitige Existenz
• Agenten verhandeln über resultierende Aktion
• Koordination mittels Blackboard
  • Agenten schreiben ihre Vorschläge auf das Blackboard
  • Agenten können die Vorschläge der anderen Agenten einsehen und ihre anpassen
  • Selektion der auszuführenden Aktion erfolgt am Blackboard (meist regelbasiert)

Hierachische organisierte Agenten

• Typischer Vertreter: Subsumption Architektur
  • strenge Hierachie vom Designer festgelegt
  • Jeder Agent entscheidet anhand der aktuellen Situation, ob sein Aktionsvorschlag auszuführen ist
  • indirekte Kommunikation zwischen den Agenten durch das Regelsystem
  • starre Verhaltensgenerierung entsprechend dem Regelsystem
  • Neudesign erforderlich bei neuen Aufgaben oder zusätzlichen Agenten

Gleichberechtigte Agenten

• strenge lokale Kooperation zwischen den Agenten
• Überlagerung aller Aktionsvorschläge zu einer resultierenden Aktion

Adaptive Aktionsauswahl mittels W-Lernen

• Wertesystem welches die zu erwartende Gesamt-Belohnung bzw -Verlust bei der Aktionsauswahl berücksichtigt
• damit kann ein Agent einen kleinen Verlust tolerieren während er damit einen großen Verlust für einen anderen Agenten verhindert
• die Q-Werte werden genutzt um die W-Werte zu ermitteln

Vorteile:

• Agenten sind selbständig
• es können Aktionen ausgewählt werden die kein Agent vorgeschlagen hat, aber der Gesamtheit zugute kommen
• leicht um weitere Agenten erweiterbar
• höhere Robustheit gegenüber dem Ausfall von Agenten (Andere übernehmen die Aufgabe)

Verarbeitungsschritte

• W-Wert repräsentiert Verlust den Agent bei Ausführung eines anderen Agenten erleiden würde
• Idee: ein Agent toleriert einen kleinen Verlust für sich und vermeidet dadurch einen großen Verlust für einen anderen Agenten

1. Ermittlung der agentenspezifischen Zustände
2. Ermittlung der agentenspezifischen Q-Wert
3. Ermittlung der W-Werte aus Q-Werten
4. Auswahl des Agenten mit maximalem W-Wert (bzw. dem Wert der der Policy entspricht)
5. Adaption der W-Werte aller Agenten (außer Gewinner, da er keinen Verlust erlitten hat)

Ermittlung der W-Werte:

• gleiche Aktionsräume -> Berechnung der Werte aus den Q-Werten -> statische W-Werte
• unterschiedliche Aktionsräume -> RL-ähnlicher Lernprozess -> dynamsiche W-Werte

statische W-Werte

Vorteile:

• alle notwendigen Werte sind schon bekannt (da aus Q-Werte berechnet wird)
• kein zeitaufwendiges Lernen der W-Werte mehr notwendig
• leichte Auswertung
• problemlose Erweiterbarkeit

Auswahlstrategien:

• Maximize best Happiness
  • maximaler individueller Gewinn zählt -> egoistisches Konzept
  • $W_{i}(s)=\max _{a\in A}Q_{i}(s,a)$
• Maximize best Profit
  • Suche nach dem größten Profit (maximaler Gewinn bei kleinstem Verlust)
• Maximize collective Happiness
  • Suche nach dem größten Gesamtgewinn aller Agenten bei Auswahl einer bestimmten Aktion
  • $W_{a}(s)=\sum Q_{i}(s,a)$
• Minimize worst Unhappiness
  • Suche nach dem größten Verlust um ihn zu Vermeiden
  • Idee ist die Auswahl des Agenten, der durch seine Nichtausführung den größten Verlust einfahren würde
  • $W_{ik}=Q_{i}(s,a_{suggested})-Q_{i}(s,a_{k})$

dynamische W-Werte

• Agent lernt die Folgen der Aktionsausführung eines anderen Experten
• Agent beobachtet, in welchen Folgezustand die Aktion eines anderen Agenten ihn gebracht hat und ermittelt den ihm dadurch entstandenen Verlust gegenüber seiner Aktion
• W-Werte werden aus real erzielten Rewards gelernt
• $W_{ik}(s)\leftarrow \underbrace {Q_{i}(s,a_{sugg})} _{ErwarteterReturn}-\underbrace {(r_{i}+\gamma \cdot \max _{b}Q_{i}(s'_{k},b))} _{ErlebterReturn}$
• Lernen erfolgt nur für die Verlierer des Wettkampfs
• W-Lernen wählt damit den Agenten aus der den kleinsten Verlust für die anderen Agenten verursacht

Vorteile:

• anwendbar auf beliebige Agenten mit unterschiedlichen Aktionsräumen
• beliebige Agentenanzahl koordinierbar

Nachteil:

• iteratives Lernen der W-Werte bedingt wiederholtes Erleben von Aktionen