Monte Carlo Methoden - inf.fu- · PDF fileMonte Carlo Methoden im Verstärkungslernen Ketill Gunnarsson [ [email protected] ], Seminar zum Verstärkungslernen, Freie Universität

Monte Carlo Methodenim Verstärkungslernen

Ketill Gunnarsson [ [email protected] ], Seminar zum Verstärkungslernen, Freie Universität Berlin [ www.inf.fu-berlin.de ]

[Spink] © Bryan Spink 2003

Ketill Gunnarsson [[email protected]], Freie Universität Berlin [ www.inf.fu-berlin.de ]

Einleitung

� Im Algemeinen ist eine Monte Carlo Methode eine stochastische Methode um Systeme zu untersuchen

� Ungefähr 100 Jahre alt

� Der Name ist inspiriert von den Casino-Roulleten in Monte Carlo


Beispiel

� Bestimmung von PI

� Berechnen die Fläche und benutzen: F = πr2

� Messen die Fläche indirekt

Aus [Woller]


Beispiel

Aus [Woller]


Monte Carlo Methoden in R.L.

� Benutzt um optimale Policy zu bestimmen.

� Erzeugen Episoden.

� Lernt von Erfahrung (kein Model notwendig).

� Nur für episodische Probleme definiert

� Ein Lern-Schritt erfolgt erst nach durchlaufen einer Episode

� Laufzeit hängt nicht von der Gesamtanzahl der Zustände ab


Wiederholung

� s ist ein Zustand.

� a ist eine Aktion.

� Ein Reward ist die aktuelle Belohnung eines Zustands.

� V(s), oder Q(s,a) ist die zukunftige Belohnung die wir nach s oder (s,a) erwarten.

� Policy π, sagt welche aktion wir auführen sollen.


Optimale Policy

� Ziel: Optimal für gierige Policy bestimmen

� Wir nähern uns an die optimale Policy indem wir unsere Werte-Funktion nach und nach verbessern (optimieren).

� Annahmen: – Optimistische Anfangswerte– Unendliche Episoden


Zustands Werte-Funktionen V(s)

� Wollen Vπ(s) bestimmen.

� Idee: das Wert eines Zustands s ist die durchnittliche Belohnung die man erhällt, nachdem man s besucht hat.


Vππππ(s) bestimmen: First Visit MC

� Wollen V(s) einschätzen, mit gegebener Policy P.

� Algorithmus:P = gegebene PolicyV = Eine Zustands Werte-FunktionReward(s) = leere Liste, für alle Zustände s

While (true){

� Eine Episode mit P generieren

� Für jeden Zustand s in der Episode:– B = Reward nachdem wir s zum ersten mal

besucht haben– Füge B zu Reward(s) hinzu– V(s) = Durchschnitt( Reward(s) )}

Aus [Sutton]


Backup diagram

� Update von V(s)erfolgt erst am Endeder Episode

Endzustand

Zustand s

Aus [Sutton]


Q(s,a) : Aktion-Zustands Werte-Funktion

� Problem: Wollen policy auswerten (z.B. gierig) aber es gibt kein model.

� model nicht vorhanden -> Aktion-Zustands Paare statt Zustände bewerten:

Q(s,a)


Monte Carlo Control

� Erhalten Annäherung an die optimale Policy (greedy) indem wir:

– Werte-Funktion in Bezug auf P verbessern, und – P in Bezug auf die Werte-Funktion verbessern

Aus [Sutton]


Monte Carlo Control: Exploring Starts

Aus [Sutton]


On-Policy Bestimmung

� Optimistische Anfangswerte:– Lösung: Verändern die Policy in eine stochastische Policy

( ε-gierig ). Jede aktion hat somit eine W.keit > 0 ausgewählt zu werden (soft policy)

� Unendliche Episoden

– Lösung: Setzten voraus dass wir nach jeder Episode eine bessere Policy haben. Dann kann man Episoden ausführen bis eine bestimmte genauigkeit erreicht ist.


ε-gierig On-Policy Monte Carlo Control

Aus [Sutton]


Inkrementelle Implementierung

� MC kann inkrementell implementiert werden um Speicher zu sparen

� Benutzen gewichtete Belohnungen (Returns):

Nicht inkrementell inkrementell

Aus [Igel]


Quellen

• [Spink] Monaco, Bryan Spink http://members.lycos.co.uk/bryanspink/interrail/html/index2.html [link checked 26.04.2004]

• [Woller] The Basics of Monte Carlo Simulations, University of Nebraska-Lincoln, Physical Chemistry Lab (Chem 484), by lab TA Joy Woller, Spring 1996. http://www.chem.unl.edu/zeng/joy/mclab/mcintro.html [link checked 26.04.2004]

• [Igel] Folien von Dr. Christian Igel, Institut für Neuroinformatik, Lehrstuhl für theoretische Biologie, Ruhr-Universität Bochum, 44780 Bochum,Germany. http://www.neuroinformatik.ruhr-uni-bochum.de/ini/PEOPLE/igel/RL/Chapter5-WS0304.pdf [link checked 05.05.2004]

• [Sutton] Reinforcement Learning:An Introduction, Richard S. Sutton and Andrew G. Barto, MIT Press, Cambridge, MA, 1998, A Bradford Book. http://www-anw.cs.umass.edu/~rich/book/the-book.html [link checked 05.05.2004]

Documents

Monte Carlo Methoden - inf.fu- · PDF fileMonte Carlo Methoden im Verstärkungslernen Ketill Gunnarsson [ [email protected] ], Seminar zum Verstärkungslernen, Freie Universität