Simulationsbasierte Algorithmen zur Lösung von Markov-Entscheidungsproblemen. Zur Strategiensuche in einer Intensivstation

Masterarbeit , 2016 , 89 Seiten , Note: 2,0

BWL - Sonstiges

Bei einem Markov-Entscheidungsproblem handelt es sich um ein Entscheidungsproblem, bei dem der Nutzen eines Agenten von einer Folge von Entscheidungen abhängig ist.
Markov-Entscheidungsprobleme können zur Modellierung eines breiten Feldes von echten Problemen dienen, allerdings haben echte Probleme in der Regel sehr große Aktions- und Zustandsräume und sind damit sehr rechenaufwendig zu lösen bzw. zu approximieren.
Während der Mensch von Natur aus sehr gut darin ist, wichtige Informationen aus großen Datenmengen herauszufiltern, gestaltet sich dies für Computer schwieriger. Der Mensch besitzt die Fähigkeit, Probleme durch Kreativität und Abstraktionsvermögen sehr effizient zu lösen, während der Computer hierfür Algorithmen, also eindeutig vorgeschriebene
Handlungsvorschriften zur Problemlösung, benötigt. Die Herausforderung besteht nun darin, Algorithmen zu entwickeln, die die Gegebenheiten und Strukturen eines Problems nutzen, um dieses möglichst schnell und effizient zu lösen. Es gibt also
keinen allgemein besten Algorithmus, sondern nur Algorithmen, die zur Lösung eines bestimmten Problems besonders gut geeignet sind.
Das Problem das in dieser Arbeit untersucht wird, ist die Steuerung einer Intensivstation (oder ICU vom englischen Intensiv Care Unit). Intensivstationen sind für den Bereich
des Operations Research besonders interessant, da sie durch ihren hohen Personalbedarf und die benötigte Vielzahl an medizinischen Apparaten zu den kostenintensivsten Abteilungen im Krankenhaus gehören. Die Intensivstation verursacht 20% der Gesamtkosten eines Krankenhauses, hat aber dabei nur einen Anteil von 5% der Betten. Zu den hohen Kosten einer Intensivstation kommt hinzu, dass diese die Patienten mit
den alarmierendsten Gesundheitszuständen versorgen soll. Die Intensivstation ist also sowohl die kostenintensivste als auch die von der medizinischen Notwendigkeit bedeutsamste Station, weswegen sie sich besonders als relevanter Forschungsgegenstand eignet.
Die Frage lautet also: Wie muss ein Algorithmus aussehen, der die beste Strategie zur Entscheidungsfindung in einer Intensivstation bestimmen soll?
Um diese Fragestellung zu operationalisieren, werden zunächst die Grundlagen im theoretischen Teil erläutert. Dieser erklärt Grundbegriffe und soll als eine Einführung in das algorithmische Denken dienen. Im praktischen Teil wird als Erstes ein Modell gebildet, das die Abläufe in einer Intensivstation in Form eines Markov-Entscheidungsproblems formuliert. [...]

Inhaltsverzeichnis

1 Einleitung

2 Grundlagen
2.1 Das Markov-Entscheidungsproblern
2.1.1 Das Markov-Entscheidungsproblern im diskreten Fall
2.1.2 Das Markov-Entscheidungsproblern im stetigen Fall
2.2 Dynamische Programmierung
2.2.1 Bellman-Gleichung und der Fluch der Dimensionalität
2.2.2 Value Iteration
2.2.3 Policy Iteration

3 Simulationsbasierte Algorithmen
3.1 Bestärkendes Lernen und Simulai ionsverfahren
3.1.1 Temporal-Difference-Learning
3.1.2 Q-Learning und SARSA-Methode
3.1.3 Roi loin-Verfahren und Hindsight-Optimierung
3.2 Adaptive Algorithmen
3.2.1 Problem des n-armigen Banditen
3.2.2 Greedy- und e- Greedy-'Verfahr en
3.2.3 Boltzmann-Exploration und Referenzgewinn
3.2.4 Persuit-Verfahren
3.2.5 ľ pper-Conlidence-Bound-Sampling
3.3 Evolutionäre Algorithmen
3.3.1 Evolutionäre Policy Iteration
3.3.2 Evolutionärer Random-Policy-Search
3.3.3 Weitere evolutionäre Verfahren
3.4 SAMW Algorithmus
3.4.1 Simulierte langsame Abkühlung
3.4.2 Gewichtete-Mehrheit und multiplikative-Gewichtung
3.4.3 Beschreibung SAMW
3.5 Analyse der Laufzeiten

4 Implementierung am Beispiel: Intensivstation
4.1 Intensivstationen
4.2 Modellierung der Problemstellung
4.3 Beschreibung des Lösungsalgorithmus
4.4 Implementierung des Lösungsalgorithmus
4.4.1 Standardverfahren
4.4.2 Betrachtung verschiedener Verteilungsannahmen
4.4.3 Erweiterung 1: Betrachtung benachbarter Äste
4.4.4 Erweiterung 2: Betrachtung mehrerer Stufen
4.4.5 Erweiterung 3: ASSI

5 Evaluierung

6 Ausblick

7 Literaturverzeichnis

8 Appendix
8.1 Abbildungen
8.2 Pseudocodes
8.3 Variablenbeschreibung
8.4 Verteilurigsannahmen
8.4.1 Beschreibung des verwendeten Datensatzes
8.4.2 Verteilungsannahrne der LOS
8.4.3 Verteilungsannahrne der Ankünfte
8.5 Tests und Paranietereinstellungen

Tabellenverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Abbildungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

Abkürzungsverzeichnis

Abbildung in dieser Leseprobe nicht enthalten

1 Einleitung

Bei einem Markov-Entscheidungsproblern handelt es sich um ein Entscheidungspro­blem, bei dem der Nutzen eines Agenten von einer Folge von Entscheidungen abhängig ist. Bei den Zustandsübergängen gilt hierbei die Markov-Annahme: Das bedeutet, die Wahrscheinlichkeit einen Zustand s' vom Zustand s aus zu erreichen, ist nur vom ge­genwärtigen Zustand s und nicht von Zuständen vor s abhängig. Die Lösung dieses Markov-Entscheidungsproblems ist eine Strategie π : S ^ A die zu jedem Zustand s die Aktion a ausgibt, mit der der Gewinn über den betrachteten Zeithorizont hinweg maximiert wird, Markov-Ihn Scheidungsprobleme können zur Modellierung eines breiten Feldes von echten Problemen dienen, allerdings haben echte Probleme in der Regel sehr große Aktions- und Zustandsräume und sind damit sehr rechenaufwendig zu lösen bzw, zu approximieren.

Während der Mensch von Natur aus sehr gut darin ist, wichtige Informationen aus großen Datenmengen herauszufiltern, gestaltet sich dies für Computer schwieriger. Der Mensch besitzt die Fähigkeit, Probleme durch Kreativität und Abstraktionsvermögen sehr effizient zu lösen, während der Computer hierfür Algorithmen, also eindeutig vor­geschriebene Handlungsvorschriften zur Problemlösung, benötigt. Die Herausforderung besteht nun darin, Algorithmen zu entwickeln, die die Gegebenheiten und Strukturen eines Problems nutzen, um dieses möglichst schnell und effizient zu lösen. Es gibt also keinen allgemein besten Algorithmus, sondern nur Algorithmen, die zur Lösung eines bestimmten Problems besonders gut geeignet sind.

Das Problem das in dieser Arbeit untersucht wird, ist die Steuerung einer Intensivstati­on (oder ICU vorn englischen Intensiv Care Unit), Intensivstationen sind für den Bereich des Operations Research besonders interessant, da sie durch ihren hohen Personalbe­darf und die benötigte Vielzahl an medizinischen Apparaten zu den kostenintensivsten Abteilungen im Krankenhaus gehören. Die Intensivstation verursacht 20% der Gesamt­kosten eines Krankenhauses, hat aber dabei nur einen Anteil von 5% der Betten,¹ Zu den hohen Kosten einer Intensivstation kommt hinzu, dass diese die Patienten mit den alarmierendsten Gesundheitszuständen versorgen soll. Die Intensivstation ist also sowohl die kostenintensivste als auch die von der medizinischen Notwendigkeit bedeut­samste Station, weswegen sie sich besonders als relevanter Forschungsgegenstand eignet. Die Frage lautet also: Wie muss ein Algorithmus aussehen, der die beste Strategie zur Entscheidungsfindung in einer Intensivstation bestimmen soll?²

Um diese Fragestellung zu operationalisieren, werden zunächst die Grundlagen im theo­retischen Teil erläutert. Dieser erklärt Grundbegriffe und soll als eine Einführung in das algorithmische Denken dienen. Im praktischen Teil wird als Erstes ein Modell gebildet, das die Abläufe in einer Intensivstation in Form eines Markov-Entscheidungsproblerns formuliert. Danach wird ein Algorithmus beschrieben, der die spezifischen Eigenschaf­ten des Problems ausnutzt, um dadurch möglichst schnell eine effiziente Strategie zu finden. Anschließend wird dieser evaluiert.

Die Untersuchung verläuft hierbei wie folgt: In Kapitel 2 wird zunächst der Aufbau eines Markov-Entscheidungsproblerns erklärt, bevor dann einige Grundlagen der Dy­namischen Programmierung erläutert werden. Diese wären die grundlegende Bellman- Gleichung, welche Probleme der sogenannte “Fluch der Dimensionalität” bei deren Lö­sung hervorruft und wie die beiden Algorithmen Value- und Policy Iteration versuchen diesen zu umgehen. Kapitel 3 handelt dann von fortgeschritteneren Methoden zur Pro­blemlösung. Hierfür bietet Kapitel 3.1 zunächst eine Einführung in das bestärkende Lernen, also die Form des künstlichen Lernens die für die Generierung von Algorithmen zur Optimierung besonders von Bedeutung ist. Die Methoden des Temporal Difference Learning, des Q-Learnings und das SARSA sowie das Rollout-Verfahren werden hierbei vorgestellt. Das Kapitel 3.2 beschäftigt sich dann mit den adaptiven Verfahren. Um zu erläutern, wie adaptive Verfahren funktionieren wird zunächst das Problem des rnelir- armigen Banditen betrachtet. Danach werden die grundlegenden Verfahren: Greedy. c-Greedy, Boltzmann Exploration und Pursuit-Verfahren, erläutert. Im Anschluss folgt ein etwas detaillierterer Blick auf das ľpper-Conlidence-Bound-Sampling (UCB). Ka­pitel 3.3 befasst sich mit evolutionären Algorithmen und dabei besonders mit evolutio­närer Random-Policy-Search und evolutionärer Policy Iteration. Kapitel 3.4 bildet das letzte Kapitel des theoretischen Teils. Hier werden die Verfahren, simulierte Abkühlung und der Multiplicative-Weights-Algorithm, sowie eine Kombination aus beiden, vorge­stellt. Kapitel 4.1 ist das erste Kapitel des praktischen Teils. Hier werden zunächst die Gegebenheiten und Besonderheiten einer Intensivstation erläutert und in Kapitel 4.2 in einen Modellrahmen gebracht. In Kapitel 4.3 wird dann der Algorithmus zur Lösung des in Kapitel 4.2 formulierten Problems vorgestellt, und anschließend in Kapitel 5 wird dieser evaluiert. Dabei wird eine Sensitivitätsanalyse durchgeführt, um zu sehen wel­che Ergebnisse der Algorithmus bei verschieden gewählten Eingangspararnetern liefert. Damit ist gemeint, welche Strategien er, unter verschiedenen Bedingungen, vorschlägt. Anschließend wird diskutiert, inwieweit diese Strategien sinnvoll erscheinen. Kapitel 6 bildet den Ausblick. In diesem wird auf Fragestellungen verwiesen, die sich im Rahmen der Arbeit nicht klären ließen.

2 Grundlagen

2.1 Das Markov-Entscheidungsproblem

Markov-Entscheidungsproblerne (oder auch Markov-Hut Scheidungsprozesse oder MDPs für Markov decision processes) sind hilfreich, urn ein weites Spektrum von Optimie­rungsproblemen zu lösen. Sie können zur Modellierung von Prozessen im Bereich der Ökonomie, des Operations Research, des Ingenieurwesens, der Informatik oder der Sozi­alwissenschaft verwendet werden.³ Durch Redefinitionen einzelner Variablen kann nahe­zu jedes dynamische Programm als Markov-Entscheidungsproblem formuliert werden.^{4 5} Markov-Ketten eignen sich hierbei immer dann sehr gut zur Modellierung einer zufäl­ligen Zustandsänderungen eines Systems, falls Grund zu der Annahme besteht, dass diese Zustandsänderungen nur über einen begrenzten Zeitraum hinweg Einfluss aufein­ander haben (elementare Markov-Eigenschaft) oder sogar gedächtnislos sind (schwache Markov-Eigenschafi ). ’ Markov-Entscheidungsproblerne wurden spätestens durch Bell­mans Arbeiten in den späten 1950ern bekannt.^{6 7} Als grundlegendes Werk auf diesem Gebiet, sei auch Ronald A. Howards Buch “Dynamic Programming and Markov Pro­cesses” aus dem Jahre 1960 hervorzuheben. ' Bei Markov-Eni Scheidungsproblemen wird zwischen Problemen in diskreter Zeit (DDPs) und Problemen in stetiger (auch kontinu­ierlicher) Zeit (GDI's) unterschieden. Da das Problem im praktischen Teil als Problem in diskreter Zeit modelliert wird, liegt der Fokus der Arbeit auf DDPs. Der Vorteil einer zeitdiskreten Modellierung gegenüber einer zeitstetigen Modellierung liegt beim damit verbundenen Rechenaufwand. Im praktischen Teil wird schließlich ein MDP si­muliert. Dabei erscheint es sinnvoll, die Zustände als eine endliche Folge anzunehmen, nur diskret verteilte Zeitpunkte zu betrachten und die dazwischen liegenden Zustände als konstant anzusehen. Alles in allem bietet also die diskrete Modellierung für unse­re Simulationen in Kapitel 4.4 eine relativ genaue Abbildung des Systems, bei einem relativ geringen Rechenaufwand.⁸ Dennoch werden aber neben DDPs auch CDPs der Vollständigkeit halber kurz beschrieben.

2.1.1 Das Markov-Entscheidungsproblem im diskreten Fall

In diesem Abschnitt wird das Markov-Entscheidungsproblem für den diskreten Fall vor­gestellt. Wie in Abbildung la⁹ zu sehen, hängt die Entwicklung des zugrunde liegen­den Entscheidungsmodells hierbei generell sowohl von Entscheidungen als auch vorn Zufall ab. Liegt kein Zufall vor. spricht man von einem deterministischen Markov- EntScheidungsprozess, und wenn keinerlei Entscheidungen getroffen werden können, handelt es sich um einen einfachen Markov-Prozess,¹⁰

Ein diskretes Markov-Entscheidungsproblem ist gegeben durch einen Tupel (S, A, T, R). Es beschreibt S die Menge der Zustände mit den Zuständen s E S, A ist der Aktions­raum mit den Aktionen a E A, A(s) Ç A ist dabei die Menge der Aktionen, die im Zustand s durchgeführt werden können, T ist ein Operator zur Beschreibung des Ef­fektes einer Aktion auf jeden anderen Zustand, und Ra(s,s') ist die Auszahlung beim Übergang von Zustand s zum Zustand s'. Im deterministischen System gilt für den Operator:

T : S x A ^ S.¹¹ (2.1)

Dies bedeutet er spezifiziert für jeden Zustand und jede Aktion einen neuen Zustand. In stochastischen Systemen gilt:

T : S x A ^ Prob(S), (2.2)

der Operator gibt also lediglich eine Wahrscheinlichkeitsverteilung über die nächsten Zustände an. Hierbei ist:

Pa (s, s') = P(st+i = s' | st = s, at = a) (2.3)

die Wahrscheinlichkeit dafür, dass Aktion a in Zustand s zur Zeit t zu Zustand s' im Zeitpunkt t + 1 führen wird. Eine Strategie π ist eine Abbildung von S auf A und beschreibt, welche Aktion in welchem Zustand ausgeführt wird. Über die Wahl einer optimalen Strategie π€Π wird die Optimierung durchgeführt. Die gewählte Strategie bestimmt hierbei die zu wählenden Aktionen. Eine Folge:

π = {ft} = {fi,f2--) (2.4)

von Funktionen f E F (Menge der Funktionen) heißt deterministische Markov-Strategie, Eine Funktion:

f : S ^ A mit f (s) E A(s) E S (2.5)

nennt sich hierbei Entscheidungsregel, Nun lässt sich eine Strategie bewerten: im deter­ministischen System durch Addition der Gewinne und im stochastischen System durch Addition der zu erwartenden Gewinne, Hierfür muss das MDP entweder endlich oder diskontiert sein, da wir ansonsten unendlich Gewinne aufaddieren müssten. Es wird die Wertfunktion Vw : S ^ R als Zielfunktion definiert. Diese repräsentiert den erwarteten Wert, wenn die Strategie π aus dem Zustand s heraus verfolgt wird. Beim diskontierten unendlichen MDP lautet die Wertfunktion:

Abbildung in dieser Leseprobe nicht enthalten

Die optimale Wertfunktion ergibt sich durch Wahl der optimalen Strategie:

Abbildung in dieser Leseprobe nicht enthalten

Beziehungsweise geschrieben als obere Schranke in Abhängigkeit der optimalen Strate­gie:

V*(s) := supV(n,s). (2,8)

πeΠ

Bei endlichen MDPs gilt im letzten Zustand, da keine weiteren zukünftigen Erträge folgen:

Vr,t=o(s) = R(s,a).u (2.9)

Für alle anderen Zustände ergibt sich:

Vw,t=o(s) = R(s,a)+ T(s,a,s') · YVK,t-i(s').u (2.10) s'eS

2.1.2 Das Markov-Entscheidungsproblem im stetigen Fall

Wenn nun hingegen gefordert wird, dass der Entscheider zu jedem Zeitpunkt, und nicht nur zu diskreten Zeitpunkten, Entscheidungen treffen kann, wird ein stetiger Markov- EntScheidungsprozess benötigt. Ein stetiges Markov-Entscheidungsproblem ist gegeben durch einen Tupel (S, A, q(·, ·, )R),^{15 16} Wie beim diskreten Problem beschreibt nun wieder S den Zustandsraum, A den Aktionsraum und R den Raum der Auszahlungsfunktio­nen, Ein Zustand wird mit s bezeichnet. Die Auszahlungsfunktion R(s, a) wird nun durch s und a bestimmt, also welchen Gewinn die Aktion a im Zustand s bringt. Ein Element q(s'|s, a) bezeichnet die Übergangsratenwahrscheinlichkeit von s nach s', wenn a ausgeführt wurde. Die zu maximierende Wertfunktion lautet:

V*(s) = max(R(s,a)+ ƒ q(s'ls,a) · γν*(s')ds').u (2,11) aeA s'eS

2.2 Dynamische Programmierung

Es wird ersichtlich, dass es sich bei einem Markov-Entscheidungsproblern um ein Opti­mierungsproblem handelt, welches aus vielen gleichartigen Teilproblemen besteht. Die optimale Lösung des Markov-Entscheidungsproblems ergibt sich aus den optimalen Lö­sungen der Teilprobleme für jeden einzelnen Zustand. Damit gilt das Optimalitätsprin- zip von Bellman und die Methoden der Dynamischen Programmierung können ange­wandt werden.

In der dynamischen Programmierung werden als Erstes die optimalen Lösungen der kleinsten Teilprobleme berechnet und danach zu einer Lösung eines nächstgrößeren Teilproblems zusammengesetzt. Dieses Verfahren wird fortgesetzt, bis das ursprüngli­che Problem, in diesem Fall das Markov-Entscheidungsproblern. gelöst wird. Einmal berechnete Teilergebnisse werden hierbei gespeichert. Bei nachfolgenden Berechnun­gen gleichartiger Teilprobleme wird auf diese Zwischenlösungen zurückgegriffen, anstatt diese jedes Mal erneut zu berechnen. Im Fall eines Markov-Entscheidungsproblems be­deutet dies, dass Auszahlungen vorn Übergang zu bestimmten Zuständen gespeichert werden. Durch Einsatz der Dynamischen Programmierung werden kostspielige Rekur­sionen vermieden, da bereits bekannte Teilergebnisse wiederverwendet werden können.

2.2.1 Bellman-Gleichung und der Fluch der Dimensionalität

Da das Interesse im Folgenden auf stochastischen MDPs liegt, wird die Wertfunktion aus Abschnitt 2.1.1 (Gleichung 2,6). die so genannte Bellmann-Gleichung, explizit für einen stochastischen MDP aufgeschrieben:

Abbildung in dieser Leseprobe nicht enthalten

beziehungsweise irn Optimum:

Abbildung in dieser Leseprobe nicht enthalten

Hierbei fällt auf. dass es sich um eine Rekursion handelt.1' Dies bedeutet, der Wert νπ(s) ergibt sich durch eine Verknüpfung mit dem bereits vorhandenen Wert νπ(s'). Die rekursive Eigenschaft der Bellman-Gleichung kann mittels der Q-Funktion veran­schaulicht werden: Während νπ(s) der erwartete Wert ist, wenn aus dem Zustand s heraus der Strategie π gefolgt wird, ist Qw(s, a) der erwartetet Wert, wenn Aktion a im Zustand s ausgeführt und danach wiederum der Strategie π verfolgt wird.^{17 18} Nun wird ersichtlich, dass Qk und νπ rekursiv durch die jeweilig andere Funktion definiert werden können. Die Q-Funktion lautet:

Abbildung in dieser Leseprobe nicht enthalten

νπ(s) ergibt sich durch Ausführung der Aktion a spezifiziert durch die Strategie π und einem anschließenden Beibehalten der Strategie π:

Abbildung in dieser Leseprobe nicht enthalten

Im Optimum gilt:

Abbildung in dieser Leseprobe nicht enthalten

Daraus folgt:

Abbildung in dieser Leseprobe nicht enthalten

Bei der Bellman-Gleichung handelt es sich um eine Kontraktion,¹⁹ also um eine Abbil­dung in sich selbst. Dies ist von Bedeutung, weil diese Eigenschaft von Verfahren, welche wiederholt approximieren, genutzt wird. Dies geschieht so zum Beispiel auch bei der im Folgenden zu erläuternden Value Iteration,²⁰ Für die Lösung von Bellrnan-Gleichungen können drei verschiedene Verfahren verwendet werden. Bei CDPs ist dies mit Hilfe von Euler-Gleichungen und Euler-Operatoren möglich und mit der Methode der unbe­stimmten Koeffizienten,²¹ Bei endlichen DDPs, welche im Folgenden im Speziellen the­matisiert werden, bietet sich die Methode der Rückwärtsinduktion an. Zum Verständnis dieser Methode bietet sich eine Betrachtung des Bellmanschen Optimalitätsprinzips an: „An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision,“²² Geht man den Gedanken, class eine Entscheidungs­folge immer optimal sein muss, unabhängig davon, was die vorherigen Entscheidungen waren, bis zur letzten Entscheidung durch, wird klar, dass auch die allerletzte Ent­scheidung optimal sein muss. Nun bestimmt man für alle Zustände bis zur letzten betrachteten Periode die optimalen Entscheidungen, danach für die Vorletzte usw,, bis man am Startzeitpunkt angekommen ist. Für jeden bestimmten Startzustand so gibt es nun eine optimale Entscheidungsfolge, Dieses Verfahren maximiert zwar die Wertfunk­tion. jedoch ist es für Markov-Prozesse mit großem Zeit-. Zustands- und Aktionsraum sehr rechenaufwendig. Wenn größere Optimierungsprobleme per Rückwärtsinduktion gelöst werden sollen, muss die Zielfunktion für jede Kombination von Werten berech­net werden. Bellman sprach hierbei vorn Fluch der Dimensionalität (Original: curse of dimensionality). In einem Markov-Eni Scheidungsprozess handelt es sich nun gar um einen dreifachen Fluch der Dimensionalität. bezogen auf den Zustandsraum, den Aus­zahlungsraum und den Aktionsraum. Hat die Zustandsvariable st = (sti, st2··, sti..., stI) ƒ Dimensionen und kann L verschiedene Werte annehmen, liegen L1 verschiedene Zu­stände vor. Analog verhält es sich mit den Auszahlungen und Aktionen.2'* Darum sollen im Folgenden Algorithmen vorgestellt werden, die mittels verschiedener Heuristiken effi­zienter und schneller als einfache Rückwärtsinduktion, M a rkov-Fni Scheidungsprobleme lösen können.

2.2.2 Value Iteration

Value Iteration ist der intuitivste und am weitesten verbreitete Algorithmus der Dyna­mischen Programmierung. Für Probleme über einen begrenzten Zeithorizont, handelt es sich dabei um eine Rückwärtsinduktion mit Abbruchkriterium. Bei der Value Ite­ration wird wie folgt vorgegangen: Zunächst wird B(S) als Menge gebundener realer Wertfunktion und Φ als ein Element dieser Menge definiert. Des Weiteren definieren wir einen Operator T als T : B(S) ^ B(S) durch:

diskontierte zukünftige Wertfunktionen kleinsteobereSchranke ^ ^

Abbildung in dieser Leseprobe nicht enthalten

jetziger Gewinn

für ФсВ (S) und seS. Die Wertiterationsfunktion vom Zustand s im Iterationsschritt k bezeichnen wir als: vk (s)eB(S), Im Initialisierungsschritt wird: v0 = 0 gewählt. Für jedes seS berechnet der Algorithmus:

Abbildung in dieser Leseprobe nicht enthalten

Nun sei {vn} eine Folge von Wertiterationsfunktionen definiert durch: vn = T(vn-i) wobei n = 1, 2...· und v0eB(s) zufällig gewählt sind. Das Verfahren aktualisiert itera­tiv durch Durchführung des Operators T : B(S) ^ B(S) die gegebene Wertfunktion. Durch mehrfache Anwendung des Operators T wird eine gegebene Wertfunktion nach und nach verbessert. Es wird also für jedes veB(s) eine neue Wertfunktion durch Be­rechnung für jedes seS erreicht. Value Iteration wird deswegen auch Verfahren der wiederholten Approximationen genannt. Falls:

Abbildung in dieser Leseprobe nicht enthalten

gilt, bricht das Verfahren ab, und das aktuelle vk wird als ausreichend gut bewertet und die zugehörige Strategie ausgewählt. Hierbei ist ε ein zuvor festgelegter Schwellen­wert, Dies kann so interpretiert werden, dass eine weitere Iteration nicht mehr notwendig ist, da sich die Wertfunktionen ausreichend angeglichen haben, also konvergiert sind. Es handelt sich also um ein Fixpunktverfahren, Bei der Wahl von e besteht ein Trade­off, Je kleiner e gewählt wird, desto präziser arbeitet das Verfahren, Dies bedeutet, es werden auf der einen Seite bessere Ergebnisse erzielt, auf der anderen verlängert sich jedoch die Laufzeit des Verfahrens,²⁴ Für alle к = 1, 2, 3... erfüllt die Value Iteration Funktion:

Abbildung in dieser Leseprobe nicht enthalten

Dies bedeutet T ist eine Kontraktion, also eine Abbildung in sich selbst und führt gemäß Banachschem Fixpunktsatz²⁵ zu einer Konvergenz von vk gegen v*. Die Zeitkomplexität bei Value Iteration wächst quadratisch im Zustandsraum und linear im Aktionsraum.²⁶

2.2.3 Policy Iteration

In der Praxis hat sich gezeigt, dass die Strategie oftmals lang vor dem Gewinn zur Optimalität konvergiert,²⁷ ' Der Grund hierfür lässt sich mit folgender Überlegung ver­anschaulichen: Für einen unendlichen Zustandsraum benötigt die Value Iteration un­endlich viele Iterationen, bei einer endlichen Anzahl an Strategien, Weswegen eine Iteration über die möglichen Strategien effizienter erscheint. Um diesen Umstand zu nutzen, entstand die Methode der Policy Iteration, Es wird ein Operator definiert als Tn : B(S) ^ B(S):

Abbildung in dieser Leseprobe nicht enthalten

Hierbei wird mit Strategien operiert, nicht wie in Gleichung 2,18 mit Aktionen, Wie Abbildung 2 zeigt,²⁸ läuft das Verfahren in zwei Schritten ab: dem Evaluationsschritt (Policy Evaluation) und dem Verbesserungsschritt (Policy Improvement), Der zunächst zu erläuternde Evaluationsschritt basiert auf der Tatsache, dass für jegliche Strategie πeΠ eine einzige korrespondierende ФеВ(S) existiert, so dass für seS gilt: Tn(Φ)ϋ) = Φϋ) = Vn(s). Nun erzielt der Evaluationsschritt eine Wertfunktion Vn für eine gege­bene Strategie π durch Lösung der zugehörigen Fixpunktfunktionsgleichung über alle Zustände s:

Abbildung in dieser Leseprobe nicht enthalten

Der Verbesserungsschritt nimmt ein gegebenes π und generiert ein neues π' durch er­füllen der Bedingung T(Vn)(s) = Tn (Vn)(s). Der Schritt stellt sicher, dass die neue Wertfunktion von π' nicht schlechter sein darf als die von π. Formal geschieht dies durch die Bedingung:

Abbildung in dieser Leseprobe nicht enthalten

Policy Iteration führt, wie auf Abbildung 3 zu sehen,²⁹ beide Schritte bei jeder Iteration alternierend aus, ausgehend von einer zufälligen Strategie πο zu Beginn. Es kommt zum Abbruch sobald:

Abbildung in dieser Leseprobe nicht enthalten

dann ist die optimale Strategie gefunden.³⁰ Eine Modifikation hierzu bietet die modi­fizierte Policy Iteration oder auch optimistische Policy Iteration. Diese führt nur eine begrenzte Anzahl an Evaluierungsschritten durch.'³¹ Andere Variationen, zur Handha­bung größerer MDPs sind z. B. die Mehrstufen-Vorausschau (Multistage-lookahead)³² und die asynchrone Policy Iteration. Bei der Mehrstufen-Vorausschau wird, anstatt nur die beste Aktion für eine Stufe auszuwählen, auf mehrere Stufen vorausgeschaut, um die nach к Stufen entstehenden Kosten als finale Kosten zu betrachten. Bei der Asyn­chronen Policy Iteration wiederum kann man sowohl die Anpassung der Strategie als auch die Anpassung der Wertfunktion nur für bestimmte Zustände durchführen.³³

3 Simulationsbasierte Algorithmen

Dieses Kapitel beschäftigt sich mit komplexeren Verfahren, Die Auswahl der im Folgen­den vorgestellten sirnulationsbasierten Algorithmen ist so ausgerichtet, dass ein mög­lichst breites Spektrum verschiedener Herangehensweisen und Lösungsverfahren ver­mittelt wird. Es ist nicht möglich den einen schnellsten Algorithmus herauszufinden, da die Leistung eines Algorithmus, davon abhängt, ob er auf ein passendes Problem ange­wendet wird.³⁴ Da von Problem zu Problem verschiedene Gattungen von Algorithmen unterschiedlich leistungsfähig sind, empfiehlt sich eine Betrachtung möglichst unter­schiedlicher Verfahren und Techniken. Zunächst werden einige grundlegende Verfahren des bestärkenden Lernens erläutert, danach folgt ein Überblick über die adaptiven Ver­fahren: Diese sollen verdeutlichen wie Algorithmen im Stande sind, eine bestimmte Auswahl nicht zufällig, sondern adaptiv, also quasi mitdenkend. zu treffen. Danach werden evolutionäre Algorithmen erläutert. Diese nutzen Verfahren, die aus der Natur, speziell der Evolution, entlehnt wurden. Der Teil über die modellbezogenen adaptiven Verfahren soll ein Methode erläutern, bei der der Algorithmus in der Lage ist. ein Mo­dell und nicht nur bloße Daten zu lernen. Der Abschnitt über den SAMW-Algorithmus veranschaulicht gleich zwei Gedanken auf einmal, den der simulierten Abkühlung und den der multiplikativen Gewichtung. Bei den drei letzten Abschnitten steht vor allem die Arbeit von Chang et al. (2006) im Vordergrund. Die Algorithmen, die im Detail er­läutert werden, stammen aus dieser Arbeit und können dort nachgelesen werden. Hinzu kommen Verweise auf weitere Algorithmen anderer Autoren. Die Algorithmen der Ar­beit von Chang et al. (2006) eignen sich vor allem daher sehr gut als Grundstock, da in dieser Arbeit sehr viele unterschiedliche Arten von Algorithmen vorgestellt werden. Eine Betrachtung aller wichtigen Arbeiten auf diesem Gebiet würde den Rahmen dieser Arbeit sprengen, dennoch sollen die wichtigsten Arbeiten, die im Folgenden nicht be­sprochen werden, der Vollständigkeit halber erwähnt sein. Diese wären: Korida und Bor­ka r (1999). Bhatnagar (2005). Bertsekas (1995-1) und Bertsekas und Tsitsiklis (1996). Wobei Letztere besonders hervorzuheben ist. In Bertsekas und Tsitsiklis (1996) werden Algorithmen vorgestellt, die auf der Methode der Projizierten Belman-Gleichung beru­hen. Dabei wird der Zustandsraum durch Projektion in einen weniger dimensionalen Unterraum verkleinert. Allerdings ist diese Arbeit sehr umfangreich und kann deshalb im Rahmen dieser Arbeit nicht adäquat besprochen werden, jedoch soll die Grundidee erwähnt worden sein.

Eine Gruppe von Algorithmen, welche auch nicht im Detail beschrieben wird, sind die modellbasierten Suchmethoden (MBS). Diese zeichnen sich dadurch aus. dass mögliche Lösungen (Kandidaten) durch Nutzung eines Probabilstischen Modells ausgewählt wer­den. Dieses wird aktualisiert, indem die bisherigen Lösungen benutzt werden, um die Suche auf einen Bereich mit möglichst vielversprechenden Lösungen zu konzentrieren, Modell bezeichnet hierbei einen adaptiven stochastischen Mechanismus, um Kandida­ten zu finden und keine approximative Beschreibung der Umwelt wie z.B. beim im Kapitel 3.1 erklärten Bestärkenden Lernen.³⁵ Zu den MBS gehört auch der Ameisenal­gorithmus (engl. Ant-Colony-Optimization kurz ACO). Eine Metaheuristik, die auf dem modellhaften Verhalten von realen Ameisen bei der Futtersuche basiert.³⁶ Diese Art von Algorithmen nutzt das aus der Natur übernommene Konzept der Schwarmintelligenz. Schwarmintelligenz bedeutet eine höhere Leistung kann durch die Kooperation von meh­reren einfachen Akteuren erbracht werden, die dabei nur einen Teil zur Gesamtlösung beisteuern müssen. Bei anderen Methoden funktioniert die Parameter-Aktualisierung mittels Kreuzentropie (engl. Cross Entropy (CE) ³⁷ oder mittels Gradientenverfahren ³⁸(Stochastic Gradient Ascent).³⁹

3.1 Bestärkendes Lernen und Simulationsverfahren

Maschinelles Lernen meint die künstliche Generierung von Wissen aus Erfahrungen. Ein künstliches System lernt hierbei aus Beispielen (Samples) und ist nach Beendigung einer Lernphase in der Lage zu verallgemeinern. Das heißt es werden nicht einfach die Beispiele auswendig gelernt, sondern das System ist in der Lage. Gesetzmäßigkeiten aus den erlernten Daten zu erkennen. So kann das System auch unbekannte Daten beurtei­len. man spricht hierbei vorn Lerntransfer. Stattdessen kann das System aber auch am Lernen unbekannter Daten scheitern. Dies wird dann Überanpassung (engl, overfitting) genannnt. Die praktische Umsetzung ist mittels Algorithmen möglich. Hierbei wird zwischen Algorithmen des Überwachten Lernens, des Unüberwachten Lernens und des Bestärkenden Lernens unterschieden.⁴⁰ Im Folgenden sind Algorithmen aus der Kate­gorie des Bestärkenden Lernens (engl. Reinforcement Learning) vor allem von Interesse, da diese ohne Beispiel und Modell ihrer Umwelt verfahren können. Beim Überwachten Lernen wird eine gewünschte Soll-Vorgabe zur Evaluierung des Lernvorgangs benötigt. Dies ist beim Bestärkenden Lernen nicht notwendig. Der Algorithmus lernt dabei durch Belohnung (oder Bestrafung) eine Strategie, wie er in potenziell auftretenden Situatio­nen zu verfahren hat. um den Nutzen des Agenten, gemeint ist damit des Systems, zu welchem die Lernkomponente gehört, zu maximieren.⁴¹

Man kann zwischen aktivem und passivem Lernen unterscheiden. Beim passiven Ler­nen handelt der Agent gemäß einer gegebenen Strategie π und versucht zu lernen wie gut diese Strategie ist. indem er beobachtet, wie sich die Zustände in der Folge verän­dern. wie z. B. bei der Policy Evaluierung in der Policy Iteration. Beim aktiven Lernen versucht der Agent eine möglichst optimale Strategie zu finden, indem er verschiede­ne Aktionen ausprobiert. Des Weiteren ist zwischen modellbasiertem und modellfreiem Lernen zu unterscheiden. Beim modellbasierten Lernen soll ein approximiertes Modell aus Erfahrungen erlernt werden. Danach wird für die entsprechenden Werte gerechnet, unter der Annahme, dass das erlernte Modell korrekt ist. Beim modellfreiem Lernen wird hingegen ohne Modell gelernt, allein aus den Erfahrungswerten heraus. Außerdem lässt sich unterscheiden, ob das Lernen on-policy oder off-policy stattfindet. Findet das Lernen on-policy statt, lernt der Agent den Wert einer Strategie aus realen Aktionen. Im Gegensatz dazu bedeutet off-policy. dass der Agent aus hypothetischen Aktionen unab­hängig von realen Aktionen lernt. Man spricht dabei auch von Online Lernen (während der Interaktion und mit der Umgebung) und Offline Lernen (vorher und ohne Umge­bung).⁴²

3.1.1 Temporal-Difference-Learning

Die Fern pora I-Di If'enence-Learning-Mel hode wird für die Schätzung von Wertfunktio­nen benutzt. Ohne Schätzung müsste der Agent bis zum letzten berechneten Gewinn abwarten bis er die Zustands-Aktions-Paare aktualisieren kann. Beim Temporal Diffe­rence Learning (kurz TD-Learning) handelt es sich um eine auf Vorhersagen basierte Methode des maschinellen Lernens. Diese kombiniert Ideen der Monte-Carlo-Methode und der Dynamischen Programmierung. Sie ähnelt der Monte-Carlo-Methode einer­seits. weil sie lernt. Stichproben der Umwelt gemäß einer Strategie zu sammeln und der Dynamischen Programmierung andererseits, da sie ihre gegenwärtigen Schätzun­gen basierend auf früher erlernten Schätzungen approximiert. Als Voraussageniet hode berücksichtigt TD-Learning. dass aufeinanderfolgende Vorhersagen oft in irgendeiner Weise korreliert sind. Die Idee ist es nun. die Vorhersagen so anzupassen, dass sie mit besseren zukünftigen Vorhersagen übereinstimmen. Es handelt sich um eine Form des Bootstrapping.⁴³

Nun sei kurz erläutert wie das TD-Learning verfährt. Es sei rt die Verstärkung zum Zeitpunkt t, in anderen Worten, der tatsächlich bisher erzielte Gewinn. Des Weiteren sei Vt die korrekte Vorhersage, die gleich der Summe aller diskontierten zukünftigen Verstärkungen ist:

Abbildung in dieser Leseprobe nicht enthalten

Zusätzlich lässt sich noch ein Vergessensparameter λ einführen mit 0 ^ Λ ^ 1. Dann wird vom TD-Lambda-Algorithmus gesprochen. Bei λ = 0 werden alte Vorhersagen sehr schnell vergessen und nur die aktuelle Schätzung berücksichtigt, und bei λ = 1 werden auch weit zurückliegende Schätzungen gleich gewichtet. Das praktische am TD- Learning ist, dass es kein Modell benötigt und dabei gute Approximationen bei der Value Iteration oder beim Evaluationsschritt in der Policy Iteration ermöglicht.⁴⁴

3.1.2 Q-Learning und SARSA-Methode

Die Q-Learning-Methode funktioniert modellfrei durch Lernen einer Q-Funktion. Hierzu sei die bereits erwähnte Q-Funktion noch einmal veranschaulicht. Die Q-Funktion ist die Aktions-Wert-Funktion. Diese weist der Wahl einer bestimmten Aktion einen Wert zu. Solche Werte nennt man dann Q-Werte. Das Ausführen einer Aktion in einem spezifischen Zustand gibt dem Agenten einen Gewinn. Das Ziel des Agenten ist es diesen Gewinn zu maximieren. Dies macht er durch Erlernen, welche Aktion in welchem Zustand optimal ist. Als optimale Aktion gilt dabei in jedem Zustand die Aktion, welche den langfristig optimalen Gewinn bringt. Dieser ist die mit einem Diskontfaktor 0 ^ γ A 1 gewichtete Summe der Erwartungswerte der Gewinne. Der Algorithmus hat hierfür eine Funktion, die die Quantität der Zustands-Aktions-Kombinationen berechnet: Q : S x A ^ R. Vor Beginn des Lernens wählt Q einen zufälligen Wert, welcher von außen zufällig oder möglicherweise mit irgendeiner Heuristik bestimmt wird. Jedes Mal, wenn der Agent eine Aktion auswählt und betrachtet wie ein Gewinn in einem neuen Zustand erzielt wird, dieser Umstand dabei möglicherweise mit dem vorherigen Zustand und der ausgeführten Aktion in Zusammenhang steht, wird Q aktualisiert. Der Grundgedanke der Methode ist eine Value Iteration mit Aktualisierung, Sie nimmt alte Werte an und macht Korrekturen basierend auf neuen Informationen:

Abbildung in dieser Leseprobe nicht enthalten

Bei Q-Learning handelt es sich um eine Variante des I'D-Learnings, die die Evaluierung von Aktionen erlaubt. Hierdurch ist eine modelfreie Strategieverbesserung möglich,⁴⁵ Der Name der State-Action-Reward-State-Action-Methode (SARSA) verdeutlicht, dass die Funktion zum Updaten der Q-Werte hierbei abhängig ist vorn: gegenwärtigen Zu­stand, der gewählten Aktion, dem Gewinn durch diese Aktion, dem neuen Zustand und der nächsten Aktion, also dem Tupel (st, at, rt, st+1, at+1). Der Agent interagiert mit der Umwelt und aktualisiert seine Strategie basierend auf der Strategie die er ausgeführt hat. Es handelt sich also um einen On-policy-learning-Algorithmus, Der Q-Wert für eine Aktion in einem Zustand Q(st, at) wird durch die Lermate α angeglichen:

Abbildung in dieser Leseprobe nicht enthalten⁴⁶

Während es sich bei Q-Learning urn einen Off-policy-Algorithrnus handelt, verfährt SARSA on-policy. Der maximale Gewinn für den nächsten Zustand wird bei SARSA anders als beim Q-Learning nicht zur Aktualisierung der Q-Werte verwendet, Siai ides­sen wird eine neue Aktion und ein damit verbundener neuer Gewinn gewählt, durch Bestimmung derselben Strategie, welche auch die ursprüngliche Aktion bestimmt hat,⁴⁷

3.1.3 Rollout-Verfahren und Hindsight-Optimierung

An dieser Stelle sei nur kurz die Idee eines Rollouts erläutert, da das Verfahren bei der Implementierung in Kapitel 4,2 erneut aufgegriffen wird. Diese besteht darin, ei­ne heuristische Strategie durch Simulation zu verbessern. Die heuristische Strategie am Beginn bezeichnet man als Basis-Strategie (engl, base policy). Deren Performance wird in irgendeiner Form evaluiert, z, B, durch Simulation, Durch One-Step-Lookahead wird basierend darauf eine verbesserte Strategie gefunden und als Schranke verwen­det, ⁴⁸ One-Step-Lookahead (dt, einstufige Vorausschau) bezeichnet in diesem Fall die Betrachtung einer Nachbarstrategie, anhand derer die Basis-Strategie evaluiert wird.⁴⁹ Rollout meint im Deutschen ein Ausrollen, bedeutet eine verfügbare Strategie über einen erwählten Zeithorizont T < œzu simulieren. Hierbei wird die vielversprechends­te Methode in einem Online-Verfahren genutzt. Die gewählte Heuristik bildet also die Basis-Strategie die das Rollout-Verfahren in seiner wiederholten Anwendung verbessern soll. Ein Rollout mit nur einer einzigen Ausgangsstrategie ist nur gut. wenn auch diese Strategie selbst gut ist. Darum ist es möglich, wenn mehrere vielversprechende Heu­ristiken verfügbar sind, diese parallel zu benutzen und so zu einer Superheuristik zu kombinieren. Man spricht dann von einem parallelen Rollout. Ein Beispiel hierfür ist der noch zu zeigende PIRS. ein spezieller Politik-Verbesserungsschritt beim evolutio­nären Policy-Random-Search in Kapitel 3.3.2 oder auch der in Kapitel 4.2 vorgestellte Algorithmus zur Strategiensuche für Intensivstationen.⁵⁰

Bei der Hindsight-Optimierung (HOP) handelt es sich um eine Online-Verfahren zur Aktionsauswahl. Hierbei wird eine Approximation einer Wertfunktion ausgehend für einen bestimmten Zustand gemacht. Dies geschieht durch das Samplen einer Menge nicht-stationärer deterministischer Probleme ausgehend von dem besagten Zustand. Anschließend werden diese Probleme rückblickend (engl, in hindsight) gelöst und die Werte kombiniert. Wenn die resultierenden deterministischen Probleme sehr viel ein­facher zu lösen sind als das ursprüngliche Problem, dann ist eine große Ersparnis an Rechenzeit möglich. ⁵¹

3.2 Adaptive Algorithmen

Adaptive Algorithmen stehen vor einem Trade-off zwischen Exploration und Exploi- taion. Um diesen zu erläutern wird zunächst auf das Problem des n-armigen Ban­diten eingegangen. Anschließend werden einige grundlegende Methoden der adapti­ven Auswahl vorgestellt, und zum Schluss wird als Musterbeispiel für die adaptiven Sampling-Algorithmen der Upper-Condidence-Bound-Sampling-Algorithmus ausführ­lich vorgestellt. Ziel von adaptiven Sampling-Algorithmen ist eine Schätzung der op­timalen Wertfunktion, unter der Bedingung einer endlichen Anzahl an Simulationen. Adaptives Sampling bedeutet, dass die Auswahl der Aktionen, die im Sample rnitein- bezogen werden, nicht zufällig verläuft, sondern von über die Zeit hinweg beobachte­ten Werten, bzw, mit ihnen verbundenen Wertfunktionen, abhängt. Dadurch wird ein Konvergieren der Wertfunktion schneller erreicht, als bei einer konventionellen Zufalls­auswahl der Samples. Algorithmen, die nach dieser Methode verfahren, eigenen sich besonders für MDPs mit großen Zustandsräumen und relativ kleinen Aki ionsräumen.⁵²

3.2.1 Problem des n-armigen Banditen

Zur Veranschaulichung adaptiver Algorithmen eignet sich eine Betrachtung des Pro­blems des n-armigen Banditen. Deswegen wird im Folgenden kurz auf dieses Problem eingegangen. Beim n-armigen Banditen handelt es sich um eine Verallgemeinerung des Glücksspielautomaten Einarmiger Bandit. Hierbei kann jeder Agent in jedem Schritt ei­ne Aktion a aus n möglichen Aktionen wählen, also an einem Automaten spielen. Nach jeder Aktion erhält er einen Gewinn. Dieser ist abhängig von einer festen Wahrschein­lichkeitsverteilung, welche wiederum von der gewählten Aktion abhängt. Dies bedeutet also, dass jede Aktion einen erwarteten Gewinn hat, welcher sich gemäß einer Wahr­scheinlichkeitsverteilung ergibt. Ziel des Spiels ist es, den gesamten Gewinn über einen Zeithorizont T hinweg zu maximieren. Kennt der Agent den tatsächlichen erwarteten Gewinn, wählt er immer die Aktion mit dem höchsten erwarteten Gewinn aus. Es wird jedoch angenommen, dass lediglich die Schätzungen dieser Werte bekannt sind. Es gibt nun mindestens eine Aktion a, deren geschätzter erwarteter Gewinn maximal ist. Hier­bei handelt es sich um die Greedy-Aktiori⁵³ oder Exploitation. Demgegenüber steht die Exploration, also das Wählen von Aktionen, die keine Greedy-Aktionen sind. Hierbei ist der Anteil der Explorations-Aktionen abhängig von der Genauigkeit der geschätzten erwarteten Gewinne, der Anzahl verbleibender Aktionen und der Sicherheit über diese Werte. Um den Trade-off zwischen Exploration und Exploitation formal zu beschreiben, hilft die Analyse des Regrets.⁵⁴ Ziel des Suchprozesses ist es schließlich, die Gewinnver­teilung an verschiedenen Automaten zu erkunden (Exploration) und gleichzeitig den Automaten zu betätigen, der bisher die höchsten empirischen Gewinne abgeworfen hat (Exploitation). Der Regret gibt hierbei den erwarteten Verlust an, der entsteht, weil nicht immer der optimale Automat gespielt wird. Sozusagen eine Art Opportunitäts­kosten gemessen an der optimalen Wahl:

Abbildung in dieser Leseprobe nicht enthalten

3.2.2 Greedy- und c-Greedy-Verfahren

Nun sollen einige einfache Methoden zur Schätzung der Wert-Funktion diskutiert wer­den. Angenommen man befindet sich im i-ten Spiel. Eine Aktion a sei ka-rnal in den vorherigen Spielen gewählt worden, wobei der Agent die Gewinne [Abbildung in dieser Leseprobe nicht enthalten] erhalten hat, dann kann der Erwartungswert der zukünftigen Gewinne E(Q(a)) durch den Mittelwert angenähert werden. Ausgehend vom Zeitpunkt t ergibt sich hierfür:

Abbildung in dieser Leseprobe nicht enthalten

Für ka wird [Abbildung in dieser Leseprobe nicht enthalten] auf einen Defaultwert gesetzt: [Abbildung in dieser Leseprobe nicht enthalten] Wächst nun [Abbildung in dieser Leseprobe nicht enthalten]. nähert sich der approximierte dem tatsächlichen Erwartungswert der Aktion an:

Abbildung in dieser Leseprobe nicht enthalten

Das Greedy-Verfahren wählt zur Zeit t die Greedy-Aktion a* mit deren Q-Funktion:

Abbildung in dieser Leseprobe nicht enthalten

Das Verfahren wählt also immer die beste bekannte Aktion aus und betreibt damit nur Exploitation,

Das e-Greedy-Verfahren wiederum wählt nur mit der Wahrscheinlichkeit (1 — e) eine Greedy-Aktion und mit der Gegenwahrscheinlichkeit e eine zufällige Aktion aus. Bei diesem Verfahren ist für t sichergestellt, dass ka und somit auch EQt(a) ^

EQ(a) konvergieren. Die Näherung der Wertfunktion E(Qt(a)) basiert auf den mittleren Gewinnen, welche der Agent in der Vergangenheit ausgezahlt bekommen hat. Eine Methode wäre nun. für jede Aktion alle Gewinne über die Zeit hinweg zu sammeln und jedes Mal erneut den Mittelwert zu berechnen:

Abbildung in dieser Leseprobe nicht enthalten

Dies ist aber Zeit und rechenaufwendig, eine Weiterentwicklung bietet die schrittweise Anpassung. Es sei nun für eine beliebige Aktion a, E(Qk) der Mittelwert der ersten k erzielten Gewinne. Damit gilt:

Abbildung in dieser Leseprobe nicht enthalten

alterWert Zielwert alterWert

Schrittweite

Für die schrittweise Implementierung sind die Werte Qk (a) sowie die Anzahl der erziel­ten Gewinne K für jede Aktion a zu speichern. Hierbei ist der Aufwand pro Aktuali­sierung einer Schätzung relativ gering. Bei der Verarbeitung des к-ten Gewinns beträgt die Schrittweite: lk = 1/k. Dies bedeutet für Aktion a ist: lk(a) = 1/ka. Die Schritt­weite konvergiert in der Folge gegen 0. Beim e-Greedy-Verfahr en sind Exploration und Exploitation einfach zu balancieren. Der Nachteil jedoch ist. dass die Auswahl gemäß einer Verteilung erfolgt, das heißt auch extrem ungünstige Aktionen können ausgewählt werden.06⁵⁵

3.2.3 Boltzmann-Exploration und Referenzgewinn

Eine Lösung hierfür bietet das Soft max-Verfahren oder auch Boltzmann-Exploration genannt. Hierbei wird zum Zeitpunkt í die Aktion a nach einer Wahrscheinlichkeit gemäß der Gibbs-Boltzmann-Verteilung

Abbildung in dieser Leseprobe nicht enthalten

ausgeführt mit τ > 0. Die Idee dahinter ist, dass die Wahrscheinlichkeitsverteilung auf den bereits geschätzten Werten E(Q(a)) beruht, wobei in der Regel die Greedy-Aktion die höchste Wahrscheinlichkeit haben soll. Dies lässt sich über den Parameter τ regeln. Wird τ sehr groß, so werden die Aktionen fast nach der Gleichverteilung ausgewählt, geht τ gegen 0 wird das Softmax-Verfahren zum Greedy-Verfahren überführt.⁵⁶ Beim Referenzgewinn-Vergleich (engl. Reward Reinforcement Comparison) ist das Ziel, Aktionen mit hohen erwarteten Gewinnen in der Zukunft häufiger und solche mit nied­rigem Gewinn dementsprechend seltener auszuführen. Damit der Agent die Gewinne bewerten kann, muss ein Referenzgewinn bestimmt werden, anhand dessen er sich ori­entieren kann. Dies kann beispielsweise der arithmetische Mittelwert aller erzielten Ge­winne ŕ sein. Der erzielte Gewinn rt wird dann als hoch empfunden, wenn er höher als der Mittelwert ist und niedrig wenn er kleiner als dieser ist. Da die Verteilung der Gewinne nicht stationär ist, wird der Mittelwert der Gewinne gewichtet berechnet:

Abbildung in dieser Leseprobe nicht enthalten

Beim Bestärkenden Lernen mit Referenzgewinnen werden zumeist nicht die Werte der Aktionen Qk(a) mit к als Anzahl der Aktionen geschätzt, sondern stattdessen ein Prä­ferenzwert wt(a) für die Akt ion a zum Zeitpunkt í. Zum Zeitpunkt í wird die Aktion at ausgeführt, wobei der Agent den Gewinn rt erhält. Danach wird Wt angepasst gemäß:

Abbildung in dieser Leseprobe nicht enthalten

Die Werte wt(a) können anschließend in eine Softmax-Funktion eingesetzt werden. Es ergibt sich die Auswahlwahrscheinlichkeit

Abbildung in dieser Leseprobe nicht enthalten

für die Aktion a zum Zeitpunkt í.⁵⁷

[...]

---

¹ Wgl. Martin (1998) S. 1.

² Mit bester Lösung ist hier, die beste Lösung, die mit relativ geringem Rechenaufwand gefunden werden kann, nicht unbedingt die ideale Lösung.

³ Agi. Chang et al. (2006) Preface III.

⁴ Vgl. Rust (1996) S. 619.

⁵ Falls sich die Frage stellt, sei kurz erwähnt, was die starke Markov-Eigenschaft vorschreibt. Um dieser Eigenschaft zu genügen, müssen zwei Zustände, die eine zufällige Stoppzeit (bei schwacher Markov- Eigenschaft nach einem deterministischen Zeitraum) auseinanderliegen, voneinander unabhängig sein.

⁶ Siehe Bellman (1957).

⁷ Siehe Howard (I960).

⁸ Vgl. Page (1991) S. 25 f.

⁹ H Siehe hierzu 8.1 Appendix: Abbildungen.

¹⁰ lüIn 8.1 Appendix: Abbildungen befindet sieh zu beiden ebenfalls eine graphische Darstellung. nffierbei gilt: S x A := {(s, a) | s E S,a E A}. Das kartesische Produkt S x A ist definiert als die Menge

¹¹ aller geordneten Paare (s, a), wob ei s ein Element aus S und a ein Element aus B ist. Diese ordnet der Operator wieder den Elementen der Menge S (Zielmenge) zu. Es handelt sich hierbei um eine äußere zweistellige Verknüpfung erster Art.

¹² ye[0,1] den Diskontfaktor dar.

¹³ Es wird rückwärts gezählt, wobei 0 der letzte Zeitpunkt t ist.

¹⁴ Endliehe MDPs müssen, um lösbar zu sein, nicht zwingend diskontiert sein.

¹⁵ Wie auch im DDP muss hierbei der Aktions und Entseheidungsraum endlich sein.

¹⁶ Vgl. Puterman (1994) S. 53ü ff.

¹⁷ Rekursivität ist eine Eigenschaft von Konstruktionsvorschriften. Diese können dabei auf ein Produkt, das sie erzeugen, von neuem angewandt werden. Hierdurch können theoretisch unendliche Schleifen entstehen.

¹⁸ Hierbei hilft es, sich Υπ(s) als Zustands-Wertfunktion, welche den Wert eines Zustands angibt, im Gegensatz zur Aktions-Wertfunktion Qπ(s,a), die den Wert einer Aktion widerspiegelt, vorzustellen.

“’Definition: Kontraktion (M,d) sei ein metrischer Raum. Eine Abbildung φ : M ^ M heißt Kontraktion, wenn es eine Zahl Ae[0,1] gibt, mit der für alle x, yeM gilt: ά(φ(χ),άφ(y) < λ · d(x,y). Man nennt die Abbildung dann kontrahierend auf M.

¹⁹ Das bedeutet, bei mehrfacher Anwendung der Abbildungsvorschrift, zieht sich die Menge in sich selbst zusammen.

²⁰ Vgl. Rust (1996) S. 622 und Denardo (1967) S. 165.

²¹ Dieses Verfahren funktioniert durch Ausprobieren. Siehe Heinemann (2015) S. 37.

²² Bellman (1957) S. 7.

²³ Vgl. hierzu Powell (2011) S. 112 ff.

²⁴ Ohne Schwellenwert würden alle möglichen Wertfunktionen berechnet, dieses Verfahren entspräche dann bei endlichem Zeithorizont der Rückwärtsinduktion.

²⁵ Zum Banachschen Fixpunktsatz siehe Kirk und Sims (2001) S. 1 ff.

²⁶ Vgl. Chang et al. (2006) S. 6 ff. Vgl. Puterman (1994) S. 160 ff. Vgl. Powell (2011) S. 68 ff. Für den Psyeudocode zur Value Iteration siehe 8.2 Appendix: Pseudocodes.

²⁷ Vgl. Pashenkova et al. (1996) S. δ.

²⁸ Für Abbildung 2 siehe 8.1 Appendix: Abbildungen.

²⁹ HFür Abbildung 3 siehe 8.1 Appendix: Abbildungen.

³⁰ UVgl. Chang et al.(2006) S. δ ff. Vgl. Puterman (1994) S. 174 ff. Siehe auch: Powell (2011) S. 74 ff. Für den Pseudocode siehe 8.2 Appendix: Pseudocodes

³¹ Siehe Bertsekas und Tsitsiklis (1996) S. 33 ff.

³² Siehe Bertsekas und Tsitsiklis (1996) S. 264.

³³ Siehe Bertsekas und Yu (2010). Für den Psyeudocode zur Policy Iteration siehe 8.2 Appendix: Pseudocodes.

³⁴ Z. B. bezüglich der Größe von Aktions- und Zustandsraum.

³⁵ Vgl. Zlochin et al. (2004) S. 374.

³⁶ Siehe Dorgio et al. (1992).

³⁷ Siehe Rubinstein (1999). Siehe De Beer et al. (2001).

³⁸ Siehe Robbins und Munro (1931). Siehe Bertsekas (1993-2).

³⁹ HVgl. Zlochin et al. (2004) S. 374 f.

⁴⁰ Vgl. Russell und Norvig (1995) S. 541 ff.

⁴¹ Vgl. Russell und Norvig (1995) S. 598 f. Zur Illustration siehe Abbildung 4 in 8.1 Appendix: Abbildungen.

⁴² Vgl. Russell und Nervig (1995) S. 605 ff.

⁴³ Dies bedeutet, dass die Aktualisierung der Wertfunktion eine existierende Schätzung nimmt und nicht

⁴⁴ den finalen Gewinn.

⁴⁵ Vgl. Sutton (1988). Vgl. Dayan (2001). Vgl. Russell und Nervig (1995) S. 604 f.

⁴⁶ Vgl. Russell und Nervig (1995) S. 612 f. Vgl. Powell (2011) S. 122 f.

⁴⁷ Zur Vergegenwärtigung der formalen Unterschiede zwischen SARSA und Q-Learning vergleiche die Gleichungen 3.5 und 3.6 miteinander.

⁴⁸ Vgl. Powell (2011) S. 124.

⁴⁹ Als untere Schranke bei Maximierungs- und als obere Schranke bei Minimierungsproblemen.

⁵⁰ HOne-Step-Lookahead meint generell das Betrachten eines Schrittes nach vorn. 5uVgl. Chang et al. (2006) S. 62 und S. 159 f. Vgl. Bertsekas (2013) S. 2989 ff.

⁵¹ Siehe Chong et al. (2000).
“Vgl. Chang et al. (2006) S. 17.

⁵² Auf deutsch kann dies mit gierige Aktion übersetzt werden. Dies ist darauf zurückzuführen, dass Gewinne sofort mitgenommen werden.

⁵³ Auf deutsch bedeutet dies: das Bedauern.

⁵⁴ Vgl. Kocsis und Szepesvári (2006) S. 282 ff. Vgl. Kuleshov und Preeup (2000) S. 1 ff. Vgl. Chang et al. (2006) S. 19 f. Vgl. Auer et al. (2002) S. 235 f. Vgl. Lai und Robbins (1985) S. 4 ff.

⁵⁵ Vgl. Kuleshov und Precup (2000) S. 6.

⁵⁶ Vgl. Vermorel und Mohri (2003) S. 440 f. Vgl. Kuleshov und Precup (2000) S. 6 f.

⁵⁷ Vgl. Kuleshov und Precup (2000) S. 6 f.

• Hochschule: Universität Augsburg
• Note: 2,0
• Autor: M.Sc. Franz Schmid (Autor:in)
• Erscheinungsjahr: 2016
• Seiten: 89
• Katalognummer: V334308
• ISBN (eBook): 9783668249080
• ISBN (Buch): 9783668249097
• Sprache: Deutsch
• Schlagworte: simulationsbasierte, algorithmen, lösung, markov-entscheidungsproblemen, strategiensuche, intensivstation