Warum gibt es immer mindestens eine Richtlinie, die besser oder gleich allen anderen Richtlinien ist?

13

Reinforcement Learning: Eine Einführung. Zweite Auflage, in Bearbeitung . Richard S. Sutton und Andrew G. Barto (c) 2012, S. 67-68.

Das Lösen einer Bestärkungslernaufgabe bedeutet ungefähr, eine Politik zu finden, die auf lange Sicht eine Menge Belohnung bringt. Für endliche MDPs können wir eine optimale Richtlinie auf folgende Weise präzise definieren. Wertefunktionen definieren eine teilweise Anordnung über Richtlinien. Eine Richtlinie π ist als besser oder gleich einer Richtlinie π wenn ihre erwartete Rendite für alle Zustände größer oder gleich der von π ist. Mit anderen Worten, ππ , wenn und nur wenn vπ(s)vπ(s) für alle sS .Es gibt immer mindestens eine Richtlinie, die besser oder gleich allen anderen Richtlinien ist.Dies ist eine optimale Politik.

Warum gibt es immer mindestens eine Richtlinie, die besser oder gleich allen anderen Richtlinien ist?

sh1ng
quelle
Ein sehr detaillierter Beweis (der Banachs Fixpunktsatz verwendet) ist in Kapitel 6.2 von "Markov Decision Processes" von Puterman zu finden.
Toghs

Antworten:

3

Gleich nach dem zitierten Teil erfahren Sie im selben Absatz, worum es sich bei dieser Richtlinie handelt: Es ist die Richtlinie, die in jedem Bundesstaat die besten Maßnahmen ergreift. In einem MDP wirkt sich die Aktion, die wir in einem Bundesstaat ausführen, nicht auf die Belohnungen für Aktionen aus, die in anderen Bundesstaaten ausgeführt werden, sodass wir die Richtlinie einfach von Bundesstaat zu Bundesstaat maximieren können.

Don Reba
quelle
Ist diese Antwort nicht völlig falsch? Wie können Sie sagen, dass die Optimierung der Richtlinienstatus zu optimalen Richtlinien führt? Wenn ich über den Zustand optimiere Stund es dauert, bis ich St+1 und dann bei optimiere, St+1führt dies zu einer optimalen Wertfunktion Vt+1 aber es gibt eine andere Politik, bei der St suboptimal zu Sl und dem Optimum führt Wertfunktion von Sl ist höher als Vt+1 . Wie können Sie dies durch eine solche flüchtige Analyse ausschließen?
MiloMinderbinder
@MiloMinderbinder Wenn die optimale Richtlinie bei St besteht, zu wählen St+1, ist der Wert von St+1 höher als der Wert von Sl .
Don Reba
Mein Fehler. Tippfehler korrigiert: 'Ist diese Antwort nicht völlig falsch? Wie können Sie sagen, dass die Optimierung von Richtlinienstatus zu optimalen Richtlinien führt? Wenn ich über den Zustand optimiere Stund es mich zu bringt St+1und dann bei optimiere, St+1führt dies zu einer optimalen Wertefunktion Vt+2 von St+2 aber es gibt eine andere Strategie, in der St zwar führt suboptimal zu Sl+1 und damit die Wertefunktion von St+1ist höher als Vl+1 aber die Wertefunktion von St+2 ist unter dieser Richtlinie höher als unter der Richtlinie, die durch Optimieren von Zustand zu Zustand ermittelt wird. Wie ist das von Ihnen ausgeschlossen? '
MiloMinderbinder
Ich denke, die Definition von V wird dies von vornherein verhindern, da sie auch zukünftige Erträge berücksichtigen sollte.
Flying_Banana
Die Frage wäre dann: Warum gibt es ? Man kann den Banach-Fixpunktsatz nicht umgehen :-)q
Fabian Werner
10

Die Existenz einer optimalen Politik ist nicht offensichtlich. Um zu sehen, warum, beachten Sie, dass die Wertfunktion nur eine teilweise Sortierung über den Bereich von Richtlinien bietet. Das heisst:

ππvπ(s)vπ(s),sS

Da dies nur eine partielle Ordnung ist, könnte es einen Fall geben , wo zwei Richtlinien, und π 2 , nicht vergleichbar sind. Mit anderen Worten, es gibt Teilmengen des Zustandsraums S 1 und S 2, so dass:π1π2S1S2

vπ(s)vπ(s),sS1

vπ(s)vπ(s),sS2

In diesem Fall können wir nicht sagen, dass eine Richtlinie besser ist als die andere. Wenn es sich jedoch um endliche MDPs mit Funktionen mit beschränktem Wert handelt, tritt ein solches Szenario niemals auf. Es gibt genau eine optimale Wertfunktion, obwohl es mehrere optimale Richtlinien geben kann.

Um dies zu beweisen, müssen Sie den Banach-Fixpunktsatz verstehen. Für eine detaillierte Analyse verweisen wir auf .

Karthik Thiagarajan
quelle
7

Rahmen

Wir betrachten in der Einstellung von:

  • Diskrete Aktionen
  • Diskrete Zustände
  • Begrenzte Belohnungen
  • Stationäre Politik
  • Unendlicher Horizont

Die optimale Richtlinie ist definiert als: und die optimale Wertfunktion ist: V = max π V π ( s ) , s S Es kann eine Menge geben von Politiken, die das Maximum erreichen. Es gibt jedoch nur eine optimale Wertefunktion: V = V π

(1)πargmaxπVπ(s),sS
(2)V=maxπVπ(s),sS
(3)V=Vπ

Die Frage

Wie kann man beweisen, dass es mindestens ein das (1) gleichzeitig für alle s S erfüllt ?πsS

Umriss des Beweises

  1. Konstruieren Sie die optimale Gleichung , die als temporäre Ersatzdefinition der Optimalwertfunktion verwendet werden soll, und beweisen Sie in Schritt 2, dass sie der Definition gemäß Gleichung (2) entspricht.

    (4)V(s)=maxaA[R(s,a)+γsST(s,a,s)V(s)]
  2. Leiten Sie die Äquivalenz der Definition der Optimalwertfunktion über Gleichung (4) und über Gleichung (2) her.

    (Beachten Sie in der Tat, dass wir nur die Notwendigkeitsrichtung im Beweis benötigen, da die Hinlänglichkeit offensichtlich ist, da wir Gleichung (4) aus Gleichung (2) konstruiert haben.)

  3. Beweisen Sie, dass es zu Gleichung (4) eine eindeutige Lösung gibt.

  4. Durch Schritt 2 wissen wir, dass die in Schritt 3 erhaltene Lösung auch eine Lösung nach Gleichung (2) ist, so dass es sich um eine optimale Wertefunktion handelt.

  5. Aus einer Optimalwertfunktion können wir eine optimale Richtlinie wiederherstellen, indem wir die Maximiereraktion in Gleichung (4) für jeden Zustand auswählen.

Details der Schritte

1

Da , haben wir V π * ( s ) max a A Q π * ( s , a ) . Und wenn es irgendwelche ~ s , so dass V π *max a V(s)=Vπ(s)=Ea[Qπ(s,a)]Vπ(s)maxaAQπ(s,a)s~, wir können eine bessere Strategie wählen, indem wirQ (s,a)=Q π (s,a)überamaximierenVπmaxaAQπ(s,a)Q(s,a)=Qπ(s,a)a .

2

(=>)

Es folgt Schritt 1.

(<=)

wenn also erfüllt ~ V ( s ) = max a A [ R ( s , a ) + γV~ , dann ~ V ( s ) = V * ( s ) = max π V π ( s ) , s S .V~(s)=maxaA[R(s,a)+γsST(s,a,s)V~(s)]V~(s)=V(s)=maxπVπ(s),sS

Define the optimal Bellman operator as

(5)TV(s)=maxaA[R(s,a)+γsST(s,a,s)V(s)]
So our goal is to prove that if V~=TV~, then V~=V. We show this by combining two results, following Puterman[1]:

a) If V~TV~, then V~V.

b) If V~TV~, then V~V.

Proof:

a)

For any π=(d1,d2,...),

V~TV~=maxd[Rd+γPdV~]Rd1+γPd1V~
Here d is the decision rule(action profile at specific time), Rd is the vector representation of immediate reward induced from d and Pd is transition matrix induced from d.

By induction, for any n,

V~Rd1+i=1n1γiPπiRdi+1+γnPπnV~
where Pπj represents the j-step transition matrix under π.

Since

Vπ=Rd1+i=1γiPπiRdi+1
we have
V~VπγnPπnV~i=nγiPπiRdi+10 as n
So we have V~Vπ. And since this holds for any π, we conclude that
V~maxπVπ=V
b)

Follows from step 1.

3

The optimal Bellman operator is a contraction in L norm, cf. [2].

Proof: For any s,

|TV1(s)TV2(s)|=|maxaA[R(s,a)+γsST(s,a,s)V1(s)]maxaA[R(s,a)+γsST(s,a,s)V(s)]|()|maxaA[γsST(s,a,s)(V1(s)V2(s))]|γV1V2
where in (*) we used the fact that
maxaf(a)maxag(a)maxa[f(a)g(a)]

Thus by Banach fixed point theorum it follows that T has a unique fixed point.

References

[1] Puterman, Martin L.. “Markov Decision Processes : Discrete Stochastic Dynamic Programming.” (2016).

[2] A. Lazaric. http://researchers.lille.inria.fr/~lazaric/Webpage/MVA-RL_Course14_files/slides-lecture-02-handout.pdf

LoveIris
quelle
-1

Die Richtlinie ein=π(s) gibt die beste Aktion ein im Zustand ausführen s nach politik π, dh die Wertfunktion vπ(s)=maxeinEINqπ(s,ein) ist am höchsten zum Handeln ein im Zustand s.

Es gibt immer mindestens eine Richtlinie, die besser oder gleich allen anderen Richtlinien ist.

Es gibt also immer eine Politik π das gibt gleiche oder höhere erwartete Belohnungen als Politik π. Beachten Sie, dass dies dies impliziertπ könnte eine / die optimale Politik sein (π) selbst.

agold
quelle
3
How does this answer the question? You're basically repeating statements written in the quote.
nbro