Entscheidungsunterstützungssysteme IWI Frankfurt 2004 Michael Schwind EUS-Übung Yield Management und Reinforcement- Learning

Entscheidungsunterstützungssysteme IWI Frankfurt 2004

Michael Schwind

EUS-Übung

Yield Managementund Reinforcement-

Learning


Klausurrelevanter Stoff

• Lokale Optimierung, Heuristiken: A*…• Agenten: Reputationsmodell entfällt• Genetische Algorithmen, Simulated Annealing• COSA: entfällt• ANT-Optimierung• SWARM: entfällt• Yield Management, Reinforcement Learning• Kombinatorische Auktionen • Literatur:

Reinforcement Learning zur Lösung multidimensionaler Yield-Management Probleme, (Wendt, Schwind 2002)


SDP Aufgabe

Berechnen Sie für die in folgender Tabelle angegebene Nachfragewahr-scheinlichkeiten für Ihr Privatflugzeug mit 4 Sitzen die Restwertfunktion (mittels stochastischer dynamischer Programmierung) für die letzten drei Anfragen vor Abflug (stage 1, stage 2 und stage 3).

Typ Wahrscheinlichkeit

Angefragte Sitzplätze

Erlös

F1 0.2 1 Sitz 2 Geldeinheiten

F2 0.8 2 Sitze 3 Geldeinheiten


SDP Stage 1

i a*(i) V1*(i) Berechnung

0 00 0.00 0.8*0+0.2*0

1 01 0.40 0.8*0+0.2*2

2 11 2.8 0.8*3+0.2*2

3 11 2.8 0.8*3+0.2*2

4 11 2.8 0.8*3+0.2*2


Stage 2 (z.B. i=2)

a*(i) V1*(i) Berechnung

00 2.8 0.8*0+0.2*0 + 0.8*V1(2)+0.2 V1(2)

01 1.4 0.8*0+0.2*2 + 0.8*V1(2)+0.2 V1(1)

10 2.96 0.8*3+0.2*0 + 0.8*V1(0)+0.2 V1(2)

11 2.88 0.8*3+0.2*2 + 0.8*V1(0)+0.2 V1(1)


Reinforcement-Learning

– Agent ist mit der Umwelt durch eine Sensorik verbunden

– In jedem Interaktionsschritt erhält der Agent einen Input i und Rückmeldung über Umweltzustand s

– Agent wählt eine Aktion a als Output, die den Umweltzustand ändert

– Agent bekommt den Wert der Aktion durch Reinforcement Signal mitgeteilt

– Ziel des Agenten ist es längerfristig die Summe der erhaltenen Reinforcement-Signale zu optimieren


Reinforcement-Learning

Agent

Umgebung

Action

ar

Reward rZu-stand s

rt+1

st+1


Demo Reinforcement Learning


Temporal-Difference-Learning

• kombiniert Dynamische Programmierung mit Monte-Carlo-Methode

• Einteilung in Episoden• setzt am Anfang der Durchläufe für jedes V(s)

Schätzwerte• korrigiert Schätzwert für V(s,t) über Summe

aus folgendem Return und folgender Zustandswertfunktion

• Episode muss zur Bildung von Schätzwerten nicht komplett durchlaufen werden!


r8 r 1

r 3

r4

r7

)s(V t

)s(V 1t

)s(V 2t

Update-Regel: )]s(V)s(Vr[)s(V)s(V t1t1ttt

Beispiel


on- vs. off-policy learning

• On-policy-Methode:Politik, mit der das Verhalten im Entscheidungsbaum generiert wird ist mit der, mit der V(s) geschätzt wird, identisch

• Off-policy-Methode:Verhaltenspolitik und Politik, mit der V(s) geschätzt wird, sind nicht identisch: Durchlauf des Entscheidungsbaumes wird bestimmt mit Verhaltenspolitik, V(s) wird geschätzt über Schätzpolitik


Q-Learning: Off-Policy TD-Learning

• Optimaler Weg wird nicht über Update von V(s), sondern über Update von Q(s,a) bestimmt– Verhaltenspolitik bestimmt Durchlauf des

Entscheidungsbaumes– Schätzpolitik wird zum Update von Q(s,a)

verwendet– Verhaltenspolitik ist -greedy; Schätzpolitik

ist greedy– Vorteil: globales Optimum wird mit größerer

Wahrscheinlichkeit gefunden


Vorgehensweise Q-Learning

Wiederhole für jede Episode:1. Gehe von einem bestimmten s aus2. Wähle eine Aktion a, ausgehend von s und unter

Zuhilfenahme der gewählten Verhaltenspolitik

z.B. -greedy 3. Beobachte Return r und Zustand s‘4. Erstelle ein Update von Q folgendermaßen:

5. Gehe von s zu s‘

)]a,s(Q)'a,'s(Qmaxr[)a,s(Q)a,s(Q'a

1t


RL-Entscheidungsbaum Aufgabe

• Zeichen Sie einen reinforcement-lernenden Agenten in seiner Umgebung und erklären Sie die wesentlichen Merkmale des Reinforcement-Lernens

• Welchen Pfad würde ein RL-Agent durch den unten gezeigten Entscheidungsbaum wählen (nur die mit r gekennzeichneten Kanten stehen zur Auswahl), wenn er die greedy-Strategie wählt. Zeigen Sie, dass nach dem Durchschnittskriterium des Reinforcement-Lernens der gewählte Weg suboptimal ist? Welche Auswahlstrategie verhindert das beschriebene Verhalten (kurze Erklärung der Strategie)?

• Berechnen Sie den Zustandswert für den mit einem Pfeil markierten Knoten nach dem Durchlauf der Episoden (r1, r3, r7) und (r1, r4, r8), sowohl nach der First-Visit Methode als auch nach der Every-Visit Methode mit Update-Faktor a = 0,2


RL-Entscheidungsbaum Aufgabe

r8 = 5r4 = 7r1 = 3

r7 = 9

r3 = 4


RL-Entscheidungsbaum Lösung

• Greedy Pfad: r1, r4, r8 mit S/3 = 15/3• Alternativer Pfad: r1, r3, r6 mit S/3 = 16/3 -greedy Strategie:

– Die -greedy Strategie ist eine Variante der MC-Methode.

– In Zustand s wird mit einer geringen Wahrscheinlichkeit nicht die Entscheidungsvariante mit dem größten Aktionswert Q(s, a) ausgewählt, sondern eine der verbleibenden suboptimalen Entscheidungen (-greedy).

– Auch Pfade mit zunächst schlechter geschätztem Aktionswert können gewählt werden. Die Tatsache, dass bei dieser Auswahlpolitik keine Episode gänzlich ausgeschlossen ist, garantiert das Durchlaufen aller Pfade im Grenzfall.


RL-Entscheidungsbaum Lösung

• Update Regel für das every-visit MC-Verfahren V(st) V(st) + [R t - V(st)]

• First-Visit Verfahren: 6,5• Every-Visit Verfahren: 0,8*6,5 + 0,2*6 =

6,4


RL-Grid-Aufgabe

In Abbildung 1 sehen Sie eine 4 x 4 Grid-World für einen reinforcement-lernenden RoboterZudem befindet sich auf dem Beiblatt das Ergebnis von einem Simulationslauf des RL-Simulators Path-Learner.Stellen sie anhand der im Simulationsbeispiel aufgezeichneten Q-Werte die gelernte Politik in Abbildung 2 dar.Benutzen Sie dazu die in Abbildung 1 verdeutlichte Pfeildarstellung. Markieren Sie die Lage eines Hindernisses mit einem X.Die Nomenklatur der Felder ist dabei wie folgt: Q[1][2] bedeutet Position 1 horizontal und Position 2 vertikal.


RL-Grid-Aufgabe

• Abbildung 1:

• Abbildung 2:


RL-Grid Aufgabe

Simulationsbeispiel

Max number of trials: 125Max number of moves per trial: 50Actual number of trials: 125Learning Data:Learner Type: QGamma = 0.8Alpha = 0.5Current Action Strategy: Epsilon (epsilon = 0.75)Reward = 100Penalty = 0

Q Matrix: ( UP DOWN LEFTRIGHT ) Q[0][0] = { 0 20.9715 0 20.9715 } Q[0][1] = { 0 16.7772 16.7772 26.2144 } Q[0][2] = { 0 0 20.9715 32.768 } Q[0][3] = { 0 40.96 26.2144 40.9463 } Q[0][4] = { 0 51.1943 32.7679 0 } Q[1][0] = {16.7772 26.2144 0 16.7772 } Q[1][1] = {20.9715 20.9715 20.9715 0 } Q[1][2] = { 0 0 0 0 } Q[1][3] = { 32.7679 51.2 051.1972 } Q[1][4] = { 40.9419 63.9988 40.9599 0

} Q[2][0] = { 20.9715 32.768 020.9715 } Q[2][1] = { 16.7772 0 26.2144 0

} Q[2][2] = { 0 0 0 0 } Q[2][3] = { 40.9598 64 063.989 } Q[2][4] = { 51.1958 79.9998 51.1985 0

} Q[3][0] = { 26.2144 40.96 0 0

} Q[3][1] = { 0 0 0 0 } Q[3][2] = { 0 0 0 0 } Q[3][3] = { 51.1977 80 0 79.9987 } Q[3][4] = { 51.6753 100 63.9977 0 } Q[4][0] = { 32.768 0 051.2 } Q[4][1] = { 0 0 40.96 64 } Q[4][2] = { 0 0 51.2 80 } Q[4][3] = { 64 0 64 100 } Q[4][4] = { 0 0 0 0 }

Documents

Entscheidungsunterstützungssysteme IWI Frankfurt 2004 Michael Schwind EUS-Übung Yield Management und Reinforcement- Learning