1Einführung in das Reinforcement Learning

DFG-Forschungsprojekt

Einführung in das Reinforcement-Learning

2Einführung in das Reinforcement Learning

Definition

• Allgemein: Automatisierung der Bepreisung von Internetdienstleistungen im Sinne eines optimalen Ertrags-Managements

• Ziel: Kopplung der Bepreisung von Arbeitsaufträgen an Rechnersysteme mit der Auslastungsoptimierung der Ressourcen

• Instrumentarium: Stochastische Dynamische Programmierung, Reinforcement Learning, Neuronale Netze, Genetische Algorithmen

3Einführung in das Reinforcement Learning

Beispiel für Auslastungsverteilung

Lastverteilung des Rechenzentrums des Landes Niedersachsen über eine Woche

4Einführung in das Reinforcement Learning

Praxisbezug

• Grundproblem:– Last auf Rechnersystemen ist – einerseits nichtdeterministisch, (stochastisch

verteilt) – andererseits folgt sie gewissen

Gesetzmäßigkeiten bedingt durch die Verhaltensweisen der Nutzer

– z.B. Abruf von Börsenkursen ab 9 Uhr, oder Video on Demand in den Abendstunden, usw.

– Idee: Einführung einer Preisstaffel nach Angebot und Nachfrage

5Einführung in das Reinforcement Learning

Resultierende Problemstellungen

Bekannte Problemtypen: • Queueing–Probleme (zeitlich und örtlich)• Scheduling–Probleme (zeitlich und örtlich) • Routing–Probleme (örtlich) • File–Allocation–Probleme (örtlich)• Load–Balancing–Probleme (örtlich und zeitlich)

• Einwand: Diese Anwendungsbereiche sind klassische Forschungsgebiete der Informatik

• Ökonomische Sicht: Für anzufordernde Arbeitspakete werden Preise ausgehandelt

6Einführung in das Reinforcement Learning

Aufgabenumfeld

• Aufträge treffen stochastisch auf ein Netz von Rechnern und sollen dort möglichst zeitnah verarbeitet werden

• Aufträge tragen Preise (zugewiesen oder ermittelt) und haben bestimmte Ablaufdauer

• Bearbeitung der Aufträge ist in Grenzen zeitlich variabel

• Ziel: Auslastung der Rechnerkapazitäten so, dass der Ertrag maximiert wird

7Einführung in das Reinforcement Learning

Zuweisungsproblem

• Zeitpunkt des Eintreffens und Größe neuer Aufträge ist nicht bekannt

• Kleine Aufträge können größere Aufträge blockieren, falls sie zu früh angenommen werden und schmälern somit den Ertrag, wenn kein neuer Auftrag eintrifft

• Werden kleinere Aufträge nicht angenommen und kommt kein größerer Auftrag, so entgeht ebenfalls Gewinn

• Assoziiert: Verteilung der Aufträge unter den Rechnersystemen

8Einführung in das Reinforcement Learning

Lösungsansätze

• Yield-Management (YM) mit dynamischer Programmierung (DP) – Voraussetzung: Teil der zu bearbeiteten Aufträge

steht in einer Warteschleife vor dem Rechnernetz– Vorteil: Problem ist analytisch lösbar durch das

Ermitteln von Restwertfunktionen im Zusammen-hang mit dynamischer Programmierung

– Nachteil: Für größere Probleme nicht mehr in vertretbarer Zeit lösbar (evtl. nicht real-time-fähig)

– Lösung: Formulieren der analytischen Lösung durch Näherungsverfahren (NN, GA) als look-up-Tabelle

9Einführung in das Reinforcement Learning

Lösungsansätze

• Reinforcement-Learning (RL) mit DP – Voraussetzung: Eingang der Aufträge folgt, neben

der Markov-Eigenschaft auch bestimmten Mustern die sich wiederholen (Bayes-Anteil wird erwartet)

– Vorteil: Bepreisung ist in die Reinforcement-Funktion integrierbar, Problem ist in Echtzeit zu lösen, Zeithorizont der Vorlaufphase ist stufenlos verstellbar, mit steigender Einsatzzeit wächst die Performance des Systems

– Nachteil: Online-Training erforderlich, zuerst schlechtere Performance

– Lösung: Vorbereiten des Systems mit Offline-Daten

10Einführung in das Reinforcement Learning

Markov-Eigenschaft

• Markov–Eigenschaft

Zustandsübergänge sind unabhängig von den vor-

hergehenden Umweltzuständen und Entscheidungen • Markov–Kette

Kette von stochastischen Ereignissen, die ihre Vergangenheit vergisst, d.h. die Auftrittswahrschein-lichkeit eines neuen Ereignisses einer Markov–Kette (0-ter Ordnung) ist unabhängig von der Auftritts-wahrscheinlichkeit der vorhergehenden Ereignisse

11Einführung in das Reinforcement Learning

Markovsche Entscheidungsprozesse

• Markovscher Entscheidungsprozess (MDP) besteht aus:– Menge von Zuständen S– Menge von Aktionen A– Ertragsfunktion R – Zustandsübergangsfunktion T– Zustandsübergangsfunktion: Zustände werden auf

Wahrscheinlichkeiten abbildet, wobei (s) die Entscheidungspolitik in Zustand s ist. T(s, a, s’) ist die Wahrscheinlichkeit eines Zustandsübergangs von Zustand s zu Zustand s’ unter Berücksichtigung von Aktion a

12Einführung in das Reinforcement Learning

Lernen in der KI

• Lernmethoden:– Routinelernen– Lernen durch Anleitung– Lernen am Beispiel und aus Erfahrung– Analogielernen– Lernen durch Entdecken

• Lernkontrolle:– Überwachtes Lernen: Lehrer z.B.: KNN– Bestätigungslernen: Kritiker z.B.: RL– Nicht überwachtes Lernen: Beobachter z.B.: LSE

13Einführung in das Reinforcement Learning

Entscheidungsbaum

s s‘ s‘‘

a4, r4

a2 , r

2

a3, r3

a5, r5

a 1, r 1

a6, r6

Politik gibt Wahrscheinlichkeiten für Wege an, den Entscheidungsbaum zu durchlaufen

Formalisierung der Ausgangssituation

14Einführung in das Reinforcement Learning

Reinforcement-Lernen

• Bestätigungs-Lernen: – als Wissenschaft in den letzten 10 Jahren etabliert

• Ursprünge: – Kybernetik, Psychologie, Statistik,

Neurowissenschaften, KI, Robotik

• Ziel: – Programmieren von Agenten durch Belohnung und

Bestrafung ohne die Notwendigkeit der expliziten Festlegung der Aufgabendurchführung

• Methode: – Agent handelt in einem dynamischen Umfeld und lernt

durch trail-and-error

15Einführung in das Reinforcement Learning

Reinforcement-Lernen

• Reinforcement-Learning (RL)– 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

16Einführung in das Reinforcement Learning

Reinforcement-Learning und Umgebung

Agent

Umgebung

Action

ar

Reward rZu-stand s

rt+1

st+1

Reinforcement-Lernen

17Einführung in das Reinforcement Learning

RL-Modelleigenschaften

• Annahme: quasistationärer Zustand Zustandsübergänge ändern sich nicht im

Zeitablauf

• Kein überwachtes Lernen wie z.B. beim KNN, da keine Input-Output-Paare

Sammeln von Informationen über mögliche Systemzustände, Aktionen, Übergänge, Erträge

• Verwandtschaft zur KI, jedoch höheres Generalisierungsvermögen als symbolische Verfahren

18Einführung in das Reinforcement Learning

RL-Modelltypen

• Modelle mit endlichem Horizont– Optimieren des Ertrags über h Schritte:– nichtstationäre Politik, falls der Zeithorizont

h mit t gegen 0 geht, setzt begrenzte Lebensdauer des Agenten voraus

– stationäre Politik, wenn h gleitender Horizont ist

• Diskontierte Modelle mit unendl. Horizont– Optimieren des diskontierte Ertrags über unendlich

viele Schritte:

• Modelle mit durchschnittlichem Ertrag– Optimieren des Durchschnittsertrags:– Grenzfall des diskontierten Modells

h

t trE0

0t tt rE

h

t trhE

0

1

19Einführung in das Reinforcement Learning

Reinforcement–Lernen und Adaptive–Regelung

• Adaptive Regelung (Adaptive Control) Struktur des dynamischen Modells wird im Gegensatz zum Reinforcement Lernen nicht verändert, Anpassungsproblem werden auf reine Parameterschätzung reduziert (Steuerung, bzw. Regelung)

• Ausbeutung contra Erkundung (Exploitation vs. Exploration) Hauptunterschied zwischen Reinforcement Lernen und überwachtem Lernen ist die Tatsache, dass ein Reinforcement System seine Umwelt erkunden muss um seine Performance zu verbessern

20Einführung in das Reinforcement Learning

Zustands-Wert-Funktion V einer beliebigen Politik

0kt1kt

ktt ss|rEss|RE)s(V

:

a4, r4

a2 , r

2

a3, r3

a5, r5

a 1, r 1

)'s(V

)''s(V

a6, r6

)s(V

Zustands-Wert-Funktion

21Einführung in das Reinforcement Learning

:

01 ,|),(

kttkt

k aassrEasQ

a4, r4

a2 , r

2a5, r5

a 1, r 1

a3, r3

a6, r6

)a,s(Q 11

s1

s2

)a,s(Q 32

Aktions-Wert-Funktion Q einer beliebigen Politik

Aktions-Wert-Funktion

22Einführung in das Reinforcement Learning

Optimale Zustands-Wert-Funktion V* :

)s(Vmax)s(V*

aasssVrEasQ tttt , |)( ),( 1*

1*

Optimale Aktions-Wert-Funktion Q* ausgedrückt über V*:

's

*

a

* )'s(V)a,s(rmax)s(V

Optimale Zustands- und Aktions-Wert-Funktion

23Einführung in das Reinforcement Learning

Dynamische Programmierung

• Lösung eines Entscheidungsproblems: in einem Entscheidungsbaum durch Ausprobieren aller Möglichkeiten und Ermittlung des besten Wegs

• Off–line Version: Ex-ante werden möglichen Lösungen durchgerechnet und nach Vorlage (look–up-table) entschieden

• On–line Version: Während des Entscheidungs-prozesses werden neue Lösungsvarianten berechnet.

• Zustandsraum: exponentielles Wachstum

• Bellman’s curse of dimensionality: “at high dimensions every object is far to another”

24Einführung in das Reinforcement Learning

Dynamische Programmierung (DP):

Bellmanns-Optimalitätsgleichung:

'stt1t

*1t

a

* aa,ss|)s(VrEmax)s(V

Optimaler Wert des Zustandes s ist gleich dem abdiskontierten optimalen Wert des nächsten Zustandes addiert zur optimalen erwarteten Belohnung von r in t +1

Dynamische Programmierung

25Einführung in das Reinforcement Learning

Wertiteration

Algorithmus: Value-Iteration initialisiere V(s) beliebigwiederhole bis Entscheidungspolitik gut genug

wiederhole für wiederhole für

ende

ende ende

SsAa

SssVsasTasRasQ

')'()',,(),(:),(

),(max:)( asQsV a

26Einführung in das Reinforcement Learning

Wertiteration

• Abbruchbedingung des Greedy–Algorithmus – Bellmansches Residual–Kriterium <

• full-backup (FB)– Value-Iteration nach obigem Beispiel

• sample-backup (SB)– Umformung der Update–Gleichung:

• Komplexität: FB-Algorithmus: O(|S|2|A|) p.It.

)),()','(max(),(:),('

asQasQrasQasQa

27Einführung in das Reinforcement Learning

Politikiteration

Algorithmus: Policy-Iterationinitialisiere Entscheidungspolitik beliebig

wiederhole berechne die Wertfunktion der Entscheidungspolitik

löse das lineare Gleichungssystem

verbessere die Entscheidungspolitik für jeden Zustand:

bis

' '

SssVsssTssRsV

')'()'),(,())(,(:)(

Ssa sVsssTssRs'

)'()'),(,())(,(maxarg:)(' '

28Einführung in das Reinforcement Learning

Politikiteration

Eigenschaften:• Wertfunktion der Entscheidungspolitik: unendlicher

diskontierte Ertrag für jeden durch Ausübung der Entscheidungspolitik erreichten Zustand

• Lösung eines linearen Gleichungssystems• Ermittlung jeden Zustandswerts unter der aktuellen

Entscheidungspolitik Versuch die Entscheidungspolitik zu verbessern • Komplexität: Max Entscheidungspolitiken O(|S|

2|A|+|S|3) pro Iteration

SA

29Einführung in das Reinforcement Learning

Monte-Carlo-Methode

- Lernen durch Erfahrung

- Einteilung in Episoden

- kein kompletter Durchlauf des Entscheidungsbaumes notwendig sample backup

- Generierung von Durchschnitts-Returns zur Bestimmung von V(s)

- Unterteilung: first-visit Monte-Carlo

every-visit Monte-Carlo

Monte-Carlo-Methode

30Einführung in das Reinforcement Learning

first visit Monte-Carlo-Methode zur Schätzung von V

- generiere eine Episode; wähle eine Politik

- durchlaufe die gesamte Episode, bilde Durchschnittsreturns R für jedes V(s), das besucht wird, verwende dazu alle Returns, die in dieser Episode auf das jeweilige s folgen

- bei erneuten Durchläufen: bilde nur für die V(s) Durchschnittsreturns, die in vorherigen Durchläufen noch nicht besucht wurden

Monte-Carlo-Methode

31Einführung in das Reinforcement Learning

a2 , r

2

r 1 = 2

Beispiel:

r 3 = 5

r7 = 6

34,4)( sV

5,5)'s(V 6)''s(V

r4 = 4r8 = 9

9)''s(V

Monte-Carlo-Methode

32Einführung in das Reinforcement Learning

every visit Monte-Carlo-Methode zur Schätzung von V

- generiere eine Episode; wähle eine Politik

- durchlaufe die gesamte Episode, bilde Durchschnittsreturns für jedes V(s), das besucht wird, verwende dazu alle Returns, die in dieser Episode auf das jeweilige s folgen

- bei erneuten Durchläufen: bilde für jedes V(s) neue Durchschnittsreturns nach obigem Muster, egal ob das jeweilige V(s) schon existiert oder nicht

Monte-Carlo-Methode

33Einführung in das Reinforcement Learning

Beispiel:

r 3 = 5

a2 , r

2

r 1 = 2 r4 = 4

r7 = 6

r8 = 9

Update-Regel: V(st) V(st) + [Rt - V(st)]

9)''s(V 34,4alt)s(V 5,5alt)'s(V 6)''s(V

5,6neu)'s(V 5neu)s(V

Monte-Carlo-Methode

34Einführung in das 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(st) über Summe aus folgendem Return und folgender Zustands-wertfunktion

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

Temporal-Difference-Lernen

35Einführung in das Reinforcement Learning

Beispiel:

r 1

r 3

r4

r7

r8

)s(V t

)s(V 1t

)s(V 2t

Update-Regel: )]()( [ )()( 11 ttttt sVsVrsVsV

Temporal-Difference-Lernen

36Einführung in das Reinforcement 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

On/Off-Policy-Methode

37Einführung in das Reinforcement Learning

Q-Learning: Off-Policy Temporal-Difference-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

Q-Lernen

38Einführung in das Reinforcement Learning

Vorgehensweise:

Wiederhole für jede Episode:

1. Gehe von einem bestimmten s aus

2. 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:)]a,s(Q)'a,'s(Qmaxr[)a,s(Q)a,s(Q

'a1t

5. Gehe von s zu s‘

Q-Lernen

39Einführung in das Reinforcement Learning

Generalisierung

• Größere RL–Umgebungen: – unmöglich die Zustandsräume vollständig zu

enumerieren und Werte zu speichern– stetigen Zustandsräume kompakte Darstellung

• Kompressions- und Generalisierungstechniken – subsymbolische Lernverfahren: Neuronale Netze,

Fuzzy-Logik, lineare Regressionsverfahren, Nächster Nachbar Verfahren

– Kompressionsverfahren zur Merkmalsextraktion ist z.B. Hauptkomponentenanalyse (PCA)

40Einführung in das Reinforcement Learning

Komprimierung

• Abzubildenden Speicherbereiche: – S A (Entscheidungspolitik)– S R (Wertfunktion)– S x A R (Q-Funktion und Erträge)– S x A x S [0,1]

(Übergangswahrscheinlichkeiten)• Meist Abbildung im überwachten Lernverfahren

• Entscheidungspolitik: keine Input-Output Trainingspaare sind vorhanden

41Einführung in das Reinforcement Learning

Komprimierung

AuswertungNäherung der Wegkosten

von Zustand jNeuronales Netz/Näherungstabelle für

Parameter r

Zustand jJ(j,r)

J(f(i),r)Merkmalsvektor f(i)Zustand i Merkmalsextraktion

Neuronales Netz/Näherungsfkt. fürParametervektor r

J(f(i),r)Merkmalsvektor f(i)Zustand i Merkmalsextraktion

Neuronales Netz/Näherungsfkt. fürParametervektor r

42Einführung in das Reinforcement Learning

Ausblick

• Bepreisung und Optimierung von Rechnerlast ist nicht gleichzeitig möglich

stufenweise Vorgehensweise

• Evtl. Rückkopplung von Lastoptimierung mit anschließender Bepreisung

• Neuerer Ansatz: Inkorporation der Bepreisung in ein RL-Modell

• Einbeziehung von kombinatorischen Auktionsverfahren

43Einführung in das Reinforcement Learning

Literatur

• D.P.Bertsekas, J.N.Tsitsiklis, Neuro-Dynamic Programming, Athena Scientific, Belmont, MA, 1996

• M.L.Putermann, Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, New York, 1994

• R.S.Sutton, A.G. Barto, Reinforcement Learning: An Introduction, MIT Press, Cambridge, MA, 1998

• http://interactive.wiwi.uni-frankfurt.de