Dlaczego zawsze istnieje co najmniej jedna polisa, która jest lepsza lub równa od wszystkich innych polis?

Rozwiązanie zadania polegającego na uczeniu się o wzmocnieniu oznacza z grubsza znalezienie polityki, która na dłuższą metę osiągnie wiele nagród. W przypadku skończonych MDP możemy precyzyjnie zdefiniować optymalną politykę w następujący sposób. Funkcje wartości definiują częściowe uporządkowanie nad politykami. Polityka określa się lepiej niż lub równy polityki„jeśli jego powrót spodziewany jest większa lub równa , dla wszystkich państw. Innymi słowy, jeśli i tylko jeśli , dla wszystkich . Zawsze istnieje co najmniej jedna polisa, która jest lepsza lub równa wszystkim innym polisom. To jest optymalna polityka. $\pi$ $\pi'$ $\pi'$ $\pi \geq \pi'$ $v_\pi(s) \geq v_{\pi'}(s)$ $s \in \mathcal{S}$

markov-process reinforcement-learning

— sh1ng
źródło

Bardzo szczegółowy dowód (wykorzystujący twierdzenie Banacha o punkcie stałym) pojawia się w rozdziale 6.2 „Procesów decyzyjnych Markowa” Putermana.

— Toghs,

Odpowiedzi:

Tuż po cytowanym fragmencie ten sam akapit faktycznie mówi ci, na czym polega ta polityka: to ta, która podejmuje najlepsze działania w każdym stanie. W MDP działania, które podejmujemy w jednym stanie, nie wpływają na nagrody za działania podejmowane w innych, więc możemy po prostu zmaksymalizować polisę według stanu.

— Don Reba
źródło

Czy ta odpowiedź nie jest całkowicie błędna? Jak można powiedzieć, że optymalizacja stanu polityki według stanu prowadzi do optymalnej polityki. Jeśli optymalizuję ponad stan

i zajmuje mi

a następnie optymalizacja w

prowadzi do funkcji wartości optymalnej

ale istnieje inna zasada, w której

prowadzi nieoptymalnie do

i optymalnej funkcja wartości

jest wyższa niż

. Jak można wykluczyć taką pobieżną analizę?

S_{t}

$S_t$

S_{t + 1}

$S_{t+1}$

S_{t + 1}

$S_{t+1}$

V_{t + 1}

$V_{t+1}$

S_{t}

$S_t$

S_{l}

$S_l$

S_{l}

$S_l$

V_{t + 1}

$V_{t+1}$

— MiloMinderbinder

@MiloMinderbinder Jeśli optymalną polityką w

jest wybranie

, wówczas wartość

jest wyższa niż wartość

S_{t}

$S_t$

S_{t + 1}

$S_{t+1}$

S_{t + 1}

$S_{t+1}$

S_{l}

$S_l$

— Don Reba

Mój błąd. Poprawiona literówka: „Czy ta odpowiedź nie jest całkowicie błędna? Jak możesz powiedzieć, że optymalizacja stanu polityki według stanu prowadzi do optymalnej polityki? Jeśli zoptymalizuję ponad stan

i zabierze mnie do

a następnie optymalizacja przy

prowadzi do funkcji wartości optymalnej

ale istnieje inna polityka, w której

chociaż prowadzi suboptymalnie do

a zatem funkcja wartości

S_{t}

$S_t$

S_{t + 1}

$S_{t+1}$

S_{t + 1}

$S_{t+1}$

V_{t + 2}

$V_{t+2}$

S_{t + 2}

$S_{t+2}$

S_{t}

$S_t$

S_{l + 1}

$S_{l+1}$

S_{t + 1}

$S_{t+1}$ jest wyższa niż

ale funkcja wartości

jest wyższa w tej polityce niż w polityce znalezionej przez optymalizację stanu według stanu. Jak to się nazywa?

V_{l + 1}

$V_{l+1}$

S_{t + 2}

$S_{t+2}$

— MiloMinderbinder,

Myślę, że definicja

zapobiegnie temu, zanim to się wydarzy, ponieważ powinna ona uwzględniać również przyszłe zyski.

V

$V$

— Flying_Banana

Pytanie brzmiałoby zatem: dlaczego

istnieje? Nie można obejść twierdzenia Banacha o stałym punkcie :-)

q_{*}

$q_*$

— Fabian Werner

Istnienie optymalnej polityki nie jest oczywiste. Aby zobaczyć dlaczego, należy zauważyć, że funkcja wartości zapewnia tylko częściowe uporządkowanie przestrzeni polityk. To znaczy:

π^{'} \geq π ⟺ v_{π^{'}} (s) \geq v_{π} (s), \forall s \in S

$\pi' \geq \pi \iff v_{\pi'}(s) \geq v_{\pi}(s), \forall s \in S$

Ponieważ jest to tylko częściowe uporządkowanie, mogą wystąpić przypadki, w których dwie polityki i nie są porównywalne. Innymi słowy, istnieją podzbiory przestrzeni stanu, i takie, że: $\pi_1$ $\pi_2$ $S_1$ $S_2$

v_{π^{'}} (s) \geq v_{π} (s), \forall s \in S_{1}

$v_{\pi'}(s) \geq v_{\pi}(s), \forall s \in S_1$

v_{π} (s) \geq v_{π^{'}} (s), \forall s \in S_{2}

$v_{\pi}(s) \geq v_{\pi'}(s),\forall s \in S_2$

W tym przypadku nie możemy powiedzieć, że jedna polisa jest lepsza od drugiej. Ale jeśli mamy do czynienia ze skończonymi MDP z funkcjami o ograniczonej wartości, taki scenariusz nigdy nie występuje. Istnieje dokładnie jedna optymalna funkcja wartości, chociaż może istnieć wiele optymalnych zasad.

Aby to udowodnić, musisz zrozumieć twierdzenie Banacha o stałym punkcie. Aby uzyskać szczegółową analizę, patrz .

— Karthik Thiagarajan
źródło

$\newcommand{\mc}{\mathcal} \newcommand{\mb}{\mathbb}$

Oprawa

Rozważamy w kontekście:

Dyskretne działania
Stany dyskretne
Ograniczone nagrody
Polityka stacjonarna
Nieskończony horyzont

\begin{matrix} (1) & π^{*} \in \arg max_{π} V^{π} (s), \forall s \in S \end{matrix}

$\pi^\ast \in \arg \max_\pi V^\pi(s), \forall s \in \mc{S} \tag{1}$

\begin{matrix} (2) & V^{*} = max_{π} V^{π} (s), \forall s \in S \end{matrix}

$V^\ast = \max_\pi V^\pi (s), \forall s \in \mc S \tag{2}$

\begin{matrix} (3) & V^{*} = V^{π^{*}} \end{matrix}

$V^\ast = V^{\pi^\ast} \tag{3}$

Pytanie

Jak udowodnić, że istnieje co najmniej jeden który spełnia (1) jednocześnie dla wszystkich ? $\pi^\ast$ $s \in \mc{S}$

Zarys dowodu

Skonstruuj równanie optymalne, które będzie stosowane jako tymczasowa zastępcza definicja funkcji wartości optymalnej, co udowodnimy w kroku 2, że jest ona równoważna definicji za pomocą równania (2).
$\begin{matrix} (4) & V^{*} (s) = max_{a \in A} [R (s, a) + γ \sum_{s^{'} \in S} T (s, a, s^{'}) V^{*} (s^{'})] \end{matrix}$ $V^\ast(s) = \max_{a \in \mc A} [ R(s, a) + \gamma \, \sum_{s^\prime \in \mc S} T(s, a, s^\prime) V^\ast(s^\prime)] \tag{4}$
Wyznacz równoważność zdefiniowania funkcji wartości optymalnej za pomocą równania (4) i równania (2).

(Zauważ, że w rzeczywistości potrzebujemy tylko kierunku konieczności w dowodzie, ponieważ wystarczalność jest oczywista, ponieważ skonstruowaliśmy równanie (4) z równania (2).)
Udowodnij, że istnieje unikalne rozwiązanie równania (4).
W kroku 2 wiemy, że rozwiązanie uzyskane w kroku 3 jest również rozwiązaniem dla równania (2), więc jest to funkcja wartości optymalnej.
Z funkcji optymalnej wartości możemy odzyskać optymalną politykę, wybierając działanie maksymalizujące w równaniu (4) dla każdego stanu.

Szczegóły kroków

Ponieważ , mamy . A jeśli są jakieś takie, że , możemy wybrać lepszą zasady maksymalizując na . $V^\ast(s) = V^{\pi^\ast}(s) = \mb E_a [Q^{\pi^\ast}(s, a)]$ $V^{\pi^\ast}(s) \le \max_{a \in \mc A} Q^{\pi^\ast} (s, a)$ $\tilde{s}$ $V^{\pi^\ast} \neq \max_{a \in \mc A} Q^{\pi^\ast} (s, a)$ $Q^{\ast} (s, a) = Q^{\pi^\ast} (s, a)$ $a$

(=>)

Następuje krok 1.

(<=)

tzn. jeśli spełnia , następnie . $\tilde V$ $\tilde V(s) = \max_{a \in \mc A} [ R(s, a) + \gamma \, \sum_{s^\prime \in \mc S} T(s, a, s^\prime) \tilde V(s^\prime)]$ $\tilde V(s) = V^\ast(s) = \max_\pi V^\pi(s), \forall s \in \mc S$

Zdefiniuj optymalnego operatora Bellmana jako Więc naszym celem jest udowodnienie, że jeśli , to . Pokazujemy to, łącząc dwa wyniki, zgodnie z Putermanem [1]:

\begin{matrix} (5) & T V (s) = max_{a \in A} [R (s, a) + γ \sum_{s^{'} \in S} T (s, a, s^{'}) V (s^{'})] \end{matrix}

$\mc T V(s) = \max_{a \in \mc A} [ R(s, a) + \gamma \, \sum_{s^\prime \in \mc S} T(s, a, s^\prime) V(s^\prime)] \tag{5}$

\tilde{V} = T \tilde{V}

$\tilde V = \mc T \tilde V$

\tilde{V} = V^{*}

$\tilde V = V^\ast$

a) Jeśli , to . $\tilde V \ge \mc T \tilde V$ $\tilde V \ge V^\ast$

b) Jeśli , to . $\tilde V \le \mc T \tilde V$ $\tilde V \le V^\ast$

Dowód:

za)

Dla dowolnego , Tutaj jest regułą decyzyjną (profil działania w określonym czasie), jest wektorową reprezentacją natychmiastowej nagrody indukowane z a jest macierzą przejściową indukowaną z . $\pi = (d_1, d_2, ...)$

\begin{aligned} \tilde{V} & \geq T \tilde{V} = max_{d} [R_{d} + γ P_{d} \tilde{V}] \\ \geq R_{d_{1}} + γ P_{d_{1}} \tilde{V} \end{aligned}

$\begin{align} \tilde V &\ge \mc T \tilde V = \max_{d} [ R_d + \gamma \, P_d \tilde V] \\ &\ge R_{d_1} + \gamma \, P_{d_1} \tilde V \\ \end{align}$

d

$d$

R_{d}

$R_d$

d

$d$

P_{d}

$P_d$

d

$d$

Indukcyjnie, dla dowolnego , gdzie reprezentuje macierz przejścia -step w . $n$

\tilde{V} \geq R_{d_{1}} + \sum_{i = 1}^{n - 1} γ^{i} P_{π}^{i} R_{d_{i + 1}} + γ^{n} P_{π}^{n} \tilde{V}

$\tilde V \ge R_{d_1} + \sum_{i=1}^{n-1} \gamma^i P_\pi^i R_{d_{i+1}} + \gamma^n P_\pi^n \tilde V$

P_{π}^{j}

$P_\pi^j$

j

$j$

π

$\pi$

Ponieważ mamy Mamy więc . A ponieważ dotyczy to każdego , dochodzimy do wniosku, że b)

V^{π} = R_{d_{1}} + \sum_{i = 1}^{\infty} γ^{i} P_{π}^{i} R_{d_{i + 1}}

$V^\pi = R_{d_1} + \sum_{i=1}^{\infty}\gamma^i P_\pi^i R_{d_{i+1}}$

\tilde{V} - V^{π} \geq \underset{\to 0 as n \to \infty}{\underset{⏟}{γ^{n} P_{π}^{n} \tilde{V} - \sum_{i = n}^{\infty} γ^{i} P_{π}^{i} R_{d_{i + 1}}}}

$\tilde V - V^\pi \ge \underbrace{\gamma^n P_\pi^n \tilde V -\sum_{i=n}^{\infty}\gamma^i P_\pi^i R_{d_{i+1}}}_{\rightarrow 0 \ \text{as}\ n\rightarrow \infty}$

\tilde{V} \geq V^{π}

$\tilde V \ge V^\pi$

π

$\pi$

\tilde{V} \geq max_{π} V^{π} = V^{*}

$\tilde V \ge \max_\pi V^\pi = V^\ast$

Wynika z kroku 1.

Optymalnym operatorem Bellmana jest skurcz w normie , por. [2] $L_\infty$

Dowód: Dla każdej , gdzie w (*) użyliśmy faktu, że $s$

\begin{aligned} | T V_{1} (s) - T V_{2} (s) | & = | max_{a \in A} [R (s, a) + γ \sum_{s^{'} \in S} T (s, a, s^{'}) V_{1} (s^{'})] - max_{a^{'} \in A} [R (s, a^{'}) + γ \sum_{s^{'} \in S} T (s, a^{'}, s^{'}) V (s^{'})] | \\ \overset{(*)}{\leq} | max_{a \in A} [γ \sum_{s^{'} \in S} T (s, a, s^{'}) (V_{1} (s^{'}) - V_{2} (s^{'}))] | \\ \leq γ ‖ V_{1} - V_{2} ‖_{\infty} \end{aligned}

$\begin{align} \left\vert \mc T V_1(s) - \mc TV_2(s) \right\vert &= \left\vert \max_{a \in \mc A} [ R(s, a) + \gamma \, \sum_{s^\prime \in \mc S} T(s, a, s^\prime) V_1(s^\prime)] -\max_{a^\prime \in \mc A} [ R(s, a^\prime) + \gamma \, \sum_{s^\prime \in \mc S} T(s, a^\prime, s^\prime) V(s^\prime)]\right\vert \\ &\overset{(*)}{\le} \left\vert \max_{a \in \mc A} [\gamma \, \sum_{s^\prime \in \mc S} T(s, a, s^\prime) (V_1(s^\prime) - V_2(s^\prime))] \right\vert \\ &\le \gamma \Vert V_1 - V_2 \Vert_\infty \end{align}$

max_{a} f (a) - max_{a^{'}} g (a^{'}) \leq max_{a} [f (a) - g (a)]

$\max_a f(a) - \max_{a^\prime} g(a^\prime) \le \max_a [f(a) - g(a)]$

Zatem według teorii Banacha o punkcie stałym wynika, że ma unikalny punkt stały. $\mc T$

Bibliografia

[1] Puterman, Martin L. .. „Procesy decyzyjne Markowa: dyskretne stochastyczne programowanie dynamiczne”. (2016).

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

— LoveIris
źródło