Konvergenzbedingungen für Richtlinien- und Wertiterationsalgorithmen

8

Richtlinien- und Wertiterationsalgorithmen können verwendet werden, um Markov-Entscheidungsprozessprobleme zu lösen. Es fällt mir schwer, die notwendigen Bedingungen für die Konvergenz zu verstehen. Wenn sich die optimale Richtlinie in zwei Schritten (dh während der Iterationen i und i + 1 ) nicht ändert , kann daraus geschlossen werden, dass die Algorithmen konvergiert haben? Wenn nicht, wann dann?

algorithms markov-process convergence ELEC
quelle

3

Um Ihre Frage zu beantworten, lassen Sie mich zunächst einige wichtige (In-) Gleichungen aufschreiben.

Bellman-Optimalitätsgleichung:

$\begin{aligned} v_{*} (s) & = max_{a} E [R_{t + 1} + γ v_{*} (S_{t + 1}) ∣ S_{t} = s, A_{t} = a] \\ = max_{a} \sum_{s^{'}} p (s^{'} ∣ s, a) [r (s, a, s^{'}) + γ v_{*} (s^{'})] \end{aligned}$ $\begin{align} v_∗(s) &= \max_{a} \mathbb{E}[R_{t+1} + \gamma v_* (S_{t+1}) \mid S_t =s, A_t =a] \\ &= \max_{a} \sum_{s'}p(s'\mid s, a) \biggl[r(s, a, s') + \gamma v_∗(s')\biggl] \end{align}$
Dabei ist $v_*(.)$ die optimale Wertfunktion.

Theorem zur Politikverbesserung ( Pit ):

Lassen und sein jedes Paar von deterministischer Politik , so dass für all , Dann wird die Politik muss so gut wie oder besser als . Das heißt, es muss eine größere oder gleiche erwartete Rendite von allen Zuständen . $\pi$ $\pi'$ $s \in S$ $q_\pi(s, \pi'(s)) \geq v_\pi(s)$ $\pi'$ $\pi$ $s \in S: v_{\pi'} (s) \geq v_\pi(s)$

(siehe Seite 89 von Sutton & Barto, Reinforcement Learning: Ein Einführungsbuch )

Wir können eine Politik verbessern durch folgende Regel bei jedem Zustand: $\pi$

\begin{aligned} π^{'} (s) & = \arg max_{ein} q_{π} (s, ein) \\ = \arg max_{ein} \sum_{s^{'}} p (s^{'} ∣ s, ein) [r (s, ein, s^{'}) + γ v_{π} (s^{'})]] \end{aligned}

$\begin{align} \pi'(s) &= \arg \max_{a}q_π(s, a)\\ &= \arg \max_{a} \sum_{s'}p(s' \mid s, a)\biggl[r(s, a, s') + \gamma v_\pi(s')\biggl] \end{align}$

Unsere neue Richtlinie erfüllt die Bedingung von Pit und ist daher so gut oder besser als . Wenn so gut wie, aber nicht besser als , dann ist für alle . Aus unserer Definition von schließen wir, dass: $\pi'$ $\pi$ $\pi'$ $\pi$ $v_{\pi'}(s)=v_{\pi}(s)$ $s$ $\pi'$

\begin{aligned} v_{π^{'}} (s) & = max_{ein} E. [{R.}_{t + 1} + γ v_{π^{'}} ({S.}_{t + 1}) ∣ {S.}_{t} = s, {EIN}_{t} = ein]] \\ = max_{ein} \sum_{s^{'}} p (s^{'} ∣ s, ein) [r (s, ein, s^{'}) + γ v_{π^{'}} (s^{'})]] \end{aligned}

$\begin{align} v_{\pi'}(s)&=\max_{a} \mathbb{E}\biggl[R_{t+1} + \gamma v_{ \pi'}(S_{t+1}) \mid S_t =s, A_t =a \biggl]\\ &= \max_{a}\sum_{s'}p(s' \mid s, a) \biggl[r(s, a, s') + \gamma v_{π'}(s') \biggl] \end{align}$

Diese Gleichheit ist jedoch dieselbe wie die Bellman-Optimalitätsgleichung, daher muss gleich . $v_{\pi'}$ $v_*$

Aus dem oben Gesagten geht hoffentlich hervor, dass die neue Richtlinie eine der optimalen Richtlinien sein muss, wenn wir eine Richtlinie verbessern und dieselbe Wertfunktion erhalten, die wir zuvor hatten. Weitere Informationen finden Sie unter Sutton & Barto (2012).

Jan Vainer
quelle

1

Sie haben Recht: Entweder die aktuelle Wertfunktionsschätzung oder die aktuelle Richtlinienschätzung kann den Status des Algorithmus vollständig beschreiben. Jeder impliziert eine einzigartige nächste Wahl für den anderen. Aus dem unten verlinkten Papier,

"Die Richtlinieniteration wird fortgesetzt, bis ." $V_{n+1} = V_n, α_{n+1} = α_n$

https://editorialexpress.com/jrust/research/siam_dp_paper.pdf

eric_kernfeld
quelle

Konvergenzbedingungen für Richtlinien- und Wertiterationsalgorithmen

Antworten: