Markov-Entscheidungsprozess Fragen [geschlossen]

Question

alt text http://img693.imageshack.us/img693/724/markov .png

Ich bin ein wenig verwirrt über einige Punkte hier:

1. Was bedeutet es, zu sagen, dass es 70% der Zeit erfolgreich sein, wird er eine bestimmte Aktion versucht? Bedeutet es, dass jedes Mal, wenn er versucht, eine Aktion A durchzuführen, wird es 70% der Zeit zu tun, dass die Aktion A und das andere 30% hat die Wirkung, dass führt zu dem gleichen Zustand, oder einfach nur, dass es so ist, wenn er sich immer tat die Aktion A, aber nur 30% der Zeit er einfach nicht tut es? Ich hoffe, ich mache mir klar: (
2. Wie ist es möglich, mehrere aufeinanderfolgende Zustände mit dem gleichen Nutzen zu haben? Theoretisch verringert das Dienstprogramm soll nicht immer, je weiter Sie sind aus Staaten mit einer Belohnung?
3. Wissen nur die Info habe ich oben, abzuleiten ist es möglich, was das ist Abzinsungsfaktor (Gamma)? Wenn ja, wie?
4. Ist es möglich, das berechnen Belohnung für die Staaten? Wie?

Answer 1

Es ist ein Muster mit den meisten MDP Problemen zu tun hat, aber ich denke, Sie wahrscheinlich einige Informationen aus der Problembeschreibung weggelassen habe, wahrscheinlich hat es mit dem Staat zu tun, um zu erreichen Sie versuchen, oder die Art und Weise einer Episode Enden (was passiert, wenn man den Rand des Gitters läuft aus). Ich habe mein Bestes getan, um Ihre Fragen zu beantworten, aber ich habe eine Grundierung auf dem Prozess, den ich mit dieser Art von Problemen zu befassen verwenden angefügt.

Als erstes Dienstprogramm ist ein ziemlich abstraktes Maß dafür, wie viel wollen Sie in einem bestimmten Zustand sein. Es ist auf jeden Fall möglich, zwei Zustände mit den gleichen Nutzen zu haben, auch wenn Sie Dienstprogramm messen mit einfachen Heuristiken (euklidische oder Manhattan-Distanz). In diesem Fall gehe ich davon aus, dass der Gebrauchswert und Belohnung ist austauschbar.

Auf lange Sicht kann das Ziel in dieser Art von Problemen neigt zu sein, , wie Sie Ihre erwartete (langfristig) Lohn dafür maximieren? Die Lernrate, Gamma, steuert, wie viel Gewicht Sie Platz über den aktuellen Stand im Vergleich zu dem Sie am Ende möchten - effektiv können Sie von Gamma als Spektrum denken geht aus, ‚tut das, was die Vorteile mir am meisten in diesem Zeitschritt‘ , um am anderen Ende der Skala < em> ‚alle meine Optionen, und zum besten zurück‘ . Sutton und Barto da drin Buch über Verstärkung Lernen einige haben wirklich schön Erklärungen , wie dies funktioniert.

---

Bevor Sie beginnen, durch die Frage zurück und stellen Sie sicher, dass Sie die folgenden Fragen sicher beantworten können.

1. Was ist ein Staat? Wie viele Staaten gibt es?
2. Was ist eine Aktion? Wie viele Aktionen gibt es?
3. Wenn Sie im Zustand starten u, und Sie gelten eine Aktion ein, was ist die Wahrscheinlichkeit, einen neuen Zustand v erreichen?

So sind die Antworten auf die Fragen?

1. Ein Zustand ist ein Vektor (x, y). Das Gitter ist 5 von 5, so gibt es 25 Staaten.
2. Es gibt vier mögliche Aktionen, {E, N, S, W}
3. Die Wahrscheinlichkeit, erfolgreich nach einem benachbarten Zustand erreicht ist eine geeignete Maßnahme Anwendung 0,7, ist die Wahrscheinlichkeit nicht bewegt (im gleichen Zustand bleibt, ist 0,3). Unter der Annahme, (0,0) ist die linke obere Zelle und (4,4) wird der untere rechte Zelle, die folgende Tabelle zeigt eine kleine Teilmenge von allen möglichen Übergängen.

Start State Action           Final State    Probability
---------------------------------------------------
(0,0)           E               (0,0)          0.3
(0,0)           E               (1,0)          0.7
(0,0)           E               (2,0)          0
...
(0,0)           E               (0,1)          0
... 
(0,0)           E               (4,4)          0
(0,0)           N               (0,0)          0.3
...
(4,4)           W               (3,4)          0.7
(4,4)           W               (4,4)          0.3

Wie können wir prüfen, ob dieser Sinn für dieses Problem macht?

1. Überprüfen Sie, ob die Tabelle eine entsprechende Anzahl von Einträgen hat. Auf einem 5 x 5 Raster gibt es 25 Staaten und vier Aktionen, so sollte die Tabelle 100 Einträge.
2. Überprüfen Sie, für einen Startzustand / Aktionspaar nur zwei Einträge haben Nicht-Null Wahrscheinlichkeit auftretender machen, dass.

---

Bearbeiten. die Anforderung für die Übergangswahrscheinlichkeiten zu beantworten der Zielzustand. Die Notation unten geht davon aus

• v ist der Endzustand
• u ist die Quelle Zustand
• a ist die Aktion, wo es nicht erwähnt wird, ist es angedeutet, dass die Aktion angewendet nicht relevant ist.

P( v=(3,3) | u =(2,3), a=E ) = 0.7
P( v=(3,3) | u =(4,3), a=W ) = 0.7
P( v=(3,3) | u =(3,2), a=N ) = 0.7
P( v=(3,3) | u =(3,4), a=S ) = 0.7
P( v=(3,3) | u =(3,3) ) = 0.3

Answer 2

ad.1) wahrscheinlich ist es nicht, dass Roboter hat immer zu bewegen - also jene 30% sind „ah, ich jetzt ein bisschen Ruhe“ oder „es gibt keine Macht, überhaupt zu bewegen war “.

Answer 3

habe ich dieses Problem als Finite-Horizon Markov Entscheidungsprozess formuliert und gelöst es über Politik Iteration. Rechts von jeder Iteration gibt es eine farbkodierte Raster-Darstellung der empfohlenen Maßnahmen für jeden Zustand sowie die ursprüngliche Belohnung grid / Matrix.

Überprüfen Sie die letzte Politik / Strategie auf Stufe 4. Ist es mit Ihrer Intuition zu?