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