Markov-Entscheidungsprozess Fragen

Question

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

Ich bin ein wenig verwirrt über einige Punkte hier:

1. Was es zu sagen, bedeutet, dass es erfolgreich 70% der Zeit sein wird, versucht er, eine gegebene Aktion? Bedeutet es, dass jedes Mal, wenn er versucht, eine Aktion A auszuführen, 70% der Zeit diese Aktion A und die anderen 30% die Aktion ausführen, die zu demselben Zustand führt, oder nur so, als ob er es immer getan hätte die Aktion A, aber nur 30% der Zeit tut er es einfach nicht? Ich hoffe, ich mache mich klar :(
2. Wie ist es möglich, mehrere aufeinander folgende Staaten mit dem gleichen Dienstprogramm? Theoretisch sollte das Dienstprogramm nicht immer abnehmen, je weiter Sie von Staaten mit einer Belohnung sind?
3. Wissen nur die Informationen, die ich oben gab, ist es möglich zu folgern, was die Abzinsungsfaktor (Gamma)? Wenn ja, wie?
4. ist es möglich, die Belohnung für die Zustände zu berechnen? Wie?

Answer 1

Es gibt ein Muster für die meisten MDP-Probleme, aber ich denke, Sie haben wahrscheinlich einige Informationen aus der Problembeschreibung weggelassen, höchstwahrscheinlich hat es mit dem Zustand zu tun, den Sie versuchen zu erreichen, oder wie Episode endet (was passiert, wenn Sie vom Rand des Gitters ablaufen). Ich habe mein Bestes gegeben, um Ihre Fragen zu beantworten, aber ich habe einen Hinweis auf den Prozess, den ich verwende, um diese Art von Problemen zu behandeln.

Erstens Dienstprogramm ist ein ziemlich abstraktes Maß dafür, wie viel Sie in einem bestimmten Zustand sein möchten. Es ist definitiv möglich, zwei Zustände mit gleichem Nutzen zu haben, selbst wenn Sie den Nutzen mit einfachen Heuristiken messen (euklidische oder Manhattan-Distanz). In diesem Fall gehe ich davon aus, dass Nutzwert und Belohnung austauschbar sind.

Auf lange Sicht ist das Ziel in diesen Arten von Problemen tendenziell, Wie maximieren Sie Ihre erwartete (langfristige) Belohnung? Die Lernrate, Gamma, steuert, wie viel Betonung Sie auf den aktuellen Zustand im Vergleich zu dem, wo Sie gerne enden würde - effektiv können Sie sich vorstellen, Gamma als Spektrum gehen, 'die Sache, die mir am meisten Vorteile in diesem Zeitschritt ' bis zum anderen Extrem ' alle meine Optionen erkunden, und gehen Sie zurück zum besten '. Sutton und Barto in ihrem Buch auf reinforcement learning haben einige wirklich nette explanations davon, wie das funktioniert.

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

1. Was ist ein Zustand? Wie viele Staaten gibt es?
2. Was ist eine Aktion? Wie viele Aktionen gibt es?
3. Wenn Sie im Zustand u beginnen und eine Aktion a anwenden, wie groß ist die Wahrscheinlichkeit, einen neuen Zustand v zu erreichen?

Also die Antworten auf die Fragen?

1. Ein Zustand ist ein Vektor (x, y). Das Raster ist 5 zu 5, also gibt es 25 Zustände.
2. Es gibt vier mögliche Aktionen: {0, 0, 0, 0, ...,
3. Die Wahrscheinlichkeit, einen benachbarten Zustand nach Anwendung einer geeigneten Aktion erfolgreich zu erreichen, beträgt 0,7, die Wahrscheinlichkeit sich nicht zu bewegen (im gleichen Zustand bleibt 0,3). Angenommen, (0,0) ist die obere linke Zelle und (4,4) ist die untere rechte Zelle, die folgende Tabelle zeigt eine kleine Teilmenge aller möglichen Übergänge.

 
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 angemessene Anzahl von Einträgen enthält. Bei einem Raster von 5 mal 5 gibt es 25 Zustände und 4 Aktionen, also sollte die Tabelle 100 Einträge haben.
2. Überprüfen Sie, ob für ein Startzustands-/Aktionspaar nur zwei Einträge eine Wahrscheinlichkeit ungleich Null haben.

---

bearbeiten. Beantworten der Anfrage für die Übergangswahrscheinlichkeiten zu den Zielzustand. Die Notation unten annimmt

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

 
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 - d. h. diese 30% sind "ah, jetzt ruh ich mich ein bisschen aus" oder "es gab überhaupt keine Kraft, um sich zu bewegen".

Answer 3

Ich habe dieses Problem als Finite-Horizon Markov Entscheidungsprozess formuliert und gelöst es über Politik Iteration. Auf der rechten Seite jeder Iteration befindet sich eine farbkodierte Gitterdarstellung der empfohlenen Aktionen für jeden Zustand sowie das ursprüngliche Belohnungsgitter/die Matrix.

Überprüfen Sie die endgültige Strategie in Schritt 4. Stimmen sie mit Ihrer Intuition überein?