Dlaczego algorytm iteracji polityki jest zbieżny z optymalną funkcją polityki i wartości?

Czytałem notatki z wykładu Andrew Ng na temat uczenia się przez wzmacnianie i próbowałem zrozumieć, dlaczego iteracja polityki jest zbieżna z funkcją optymalnej wartości i optymalną polityką .$V^*$$\pi^*$

Przypomnijmy, że iteracja zasad to:

$\text{Initialize $\pi$ randomly} \\ \text{Repeat}\{\\ \quad Let \ V := V^{\pi} \text{ \\for the current policy, solve bellman's eqn's and set that to the current V}\\ \quad Let \ \pi(s) := argmax_{a \in A} \sum_{s'}P_{sa}(s') V(s')\\ \}$

Dlaczego algorytm zachłanny prowadzi do optymalnej polityki i funkcji optymalnej wartości? (Wiem, że zachłanne algorytmy nie zawsze to gwarantują lub mogą utknąć w lokalnych optymach, więc chciałem tylko zobaczyć dowód na jego optymalność algorytmu).

Wydaje mi się również, że iteracja polityki jest czymś analogicznym do klastrowania lub spadku gradientu. Do klastrowania, ponieważ przy obecnym ustawieniu parametrów optymalizujemy. Podobne do opadania gradientu, ponieważ po prostu wybiera wartość, która wydaje się zwiększać jakąś funkcję. Te dwie metody nie zawsze są zbieżne z optymalnymi maksimami i próbowałem zrozumieć, w jaki sposób ten algorytm różni się od poprzednich, o których wspomniałem.

---

Oto moje dotychczasowe myśli:

Powiedzmy, że zaczynamy od zasady , a następnie po pierwszym kroku, dla tej ustalonej zasady mamy:$\pi_1$

$V^{\pi_1}(s) = R(s) + \gamma \sum_{s'}P_{s\pi_1(s)}(s')V^{\pi_1}(s')$

$V^{(1)} := V^{\pi_1}(s)$

Gdzie V ^ {(1)} jest funkcją wartości dla pierwszej iteracji. Następnie po drugim kroku wybieramy nowe zasady aby zwiększyć wartość . Teraz, przy nowej polityce , jeśli zrobimy drugi krok algorytmu, zachowa się następująca nierówność:$\pi_2$$V^{\pi_1}(s)$$\pi_2$

$R(s) + \gamma \sum_{s'}P_{s\pi_1(s)}(s')V^{\pi_1}(s') \leq R(s) + \gamma \sum_{s'}P_{s\pi_2(s)}(s')V^{\pi_1}(s')$

Ponieważ wybieramy w drugim kroku, aby zwiększyć funkcję wartości w poprzednim kroku (tj. Poprawić . Jak dotąd jasne jest, że wybranie może tylko zwiększyć V ^ {(1)}, bo tak właśnie wybieramy . Jednak moje zamieszanie pojawia się w kroku powtarzania, ponieważ gdy powtórzymy i wrócimy do kroku 1, faktycznie zmieniamy wszystko całkowicie, ponieważ ponownie obliczamy dla nowej zasady . Co daje:$\pi_2$$V^{(1)}$$\pi_2$$\pi_2$$V^{2}$$\pi_2$

$V^{\pi_2}(s) = R(s) + \gamma \sum_{s'}P_{s\pi_2(s)}(s')V^{\pi_2}(s')$

ale to NIE jest:

$V^{\pi_1}(s) = R(s) + \gamma \sum_{s'}P_{s\pi_2(s)}(s')V^{\pi_1}(s')$

Co wydaje się być problemem, ponieważ wybrano do poprawy , a nie tej nowej . Zasadniczo problem polega na tym, że gwarantuje poprawę wykonując w zamian z gdy funkcja wartości to . Ale w kroku powtarzania zmieniamy na , ale nie widzę, jak to gwarantuje, że funkcja wartości poprawia się monotonicznie przy każdym powtórzeniu, ponieważ obliczono, aby poprawić funkcję wartości, gdy funkcje wartości pozostają na poziomie$\pi_2$$V^{(1)}$$V^{\pi_2}$$pi_2$$R(s) + \gamma \sum_{s'}P_{s\pi_1(s)}(s')V^{\pi_1}(s')$$\pi_2$$pi_1$$V^{\pi_1}$$V^{\pi_1}$$V^{\pi_2}$$\pi_2$$V^{\pi_1}$, ale krok 1 zmienia na (co jest złe, ponieważ poprawiłem tylko poprzednią funkcję wartości, którą mieliśmy).$V^{\pi_1}$$V^{\pi_2}$$\pi_2$

Wydaje mi się, że brakuje ci części z tego samego powodu, dla którego możemy zamówić . Zasadniczo taka jest definicja jednej polityki, która jest lepsza od innej - że jej funkcja wartości jest większa lub równa we wszystkich stanach. Zagwarantowałeś to wybierając akcje maksymalizujące - żadna wartość stanu nie może być gorsza niż poprzednio, a jeśli tylko jeden wybór akcji zmienił się, aby wybrać lepszą akcję maksymalizującą, to już wiesz (ale być może nie obliczałeś), że dla tego stanu będzie wyższy niż był dla .$V^{\pi_2} \ge V^{\pi_1}$$\pi_2 \ge \pi_1$$V^{\pi_2}(s)$$V^{\pi_1}(s)$

Kiedy zdecydujemy się zmaksymalizować wyniki w celu wygenerowania , nie wiemy, jakie będą nowe dla dowolnego stanu, ale wiemy, że .$\pi_2$$V^{\pi_2}(s)$$\forall s: V^{\pi_2}(s) \ge V^{\pi_1}(s)$

Dlatego powrót do pętli i obliczenie dla nowej zasady ma takie same lub wyższe wartości niż wcześniej, a jeśli chodzi o ponowne zaktualizowanie zasad, .$V^{\pi_2}$$\pi_3 \ge \pi_2 \ge \pi_1$

Najpierw zobaczmy, dlaczego działa algorytm iteracji zasad. Ma dwa kroki.

Etap oceny polityki:

$v_n = r_{d_n} + \gamma P_{d_n}v_n$ jest ogólną formą wektorową układu równań liniowych.

Tutaj terminy są natychmiastowymi nagrodami i odpowiadającymi im rzędami macierzy przejścia.$r_{d_n}, P_{d_n}$

Warunki te zależą od polityki$\Pi_n$

Rozwiązując powyższy układ równań, możemy znaleźć wartości$v_n$

Krok poprawy polityki:

Załóżmy, że udało nam się znaleźć nową polisę taką, że$\Pi_{n+1}$

$$\begin{align} r_{d_n+1} + \gamma P_{d_n+1}v_n & \ge r_{d_n} + \gamma P_{d_n}v_n \\ \implies r_{d_n+1} & \ge [I - \gamma P_{d_n+1}]v_n \quad \text{say this is eqn. 1}\\ \end{align}$$

Teraz, w oparciu o nowe zasady , możemy znaleźć , powiedzmy, że to jest równanie 2.$\Pi_{n+1}$$v_{n+1} = r_{d_{n+1}} + \gamma P_{d_{n+1}}v_{n+1}$

Pokażemy, że ;$v_{n+1} \ge v_n$

tzn. zasadniczo dla wszystkich stanów, nowo wybrana polityka daje lepszą wartość w porównaniu do poprzedniej polityki$\Pi_{n+1}$$\Pi_{n}$

Dowód:

Z równania 2 mamy,

$[I - \gamma P_{d_{n+1}}]v_{n+1} = r_{d_n+1}$

Od, mamy$1 \&2$

$v_{n+1} \ge v_{n}$

Zasadniczo wartości rosną monotonicznie z każdą iteracją.

Ważne jest, aby zrozumieć, dlaczego Interakcja między politykami nie utknie na poziomie lokalnym.

Polityka to nic innego jak przestrzeń działań państwa.

Na każdym etapie iteracji zasad staramy się znaleźć co najmniej jedno działanie stanu, które różni się między i i sprawdzamy, czy . Tylko jeśli warunek jest spełniony, obliczymy rozwiązanie nowego układu równań liniowych.$\Pi_{n+1}$$\Pi_{n}$$\quad r_{d_n+1} + \gamma P_{d_n+1}v_n \ge r_{d_n} + \gamma P_{d_n}v_n$

Załóżmy, że i są odpowiednio globalnym i lokalnym optimum.$\Pi^*$$\Pi^\#$

Implikuje,$v_* \ge v_\#$

Załóżmy, że algorytm utknął na lokalnym optimum.

W takim przypadku krok poprawy polityki nie zatrzyma się na lokalnej optymalnej przestrzeni działania stanu , ponieważ w istnieje co najmniej jedno działanie stanu, które jest inne niż i daje wyższą wartość porównaniu do$\Pi^\#$$\Pi^*$$\Pi^\#$$v_{*}$$v_{\#}$

lub innymi słowy

$[I-\gamma P_{d_*}]v_* \ge [I-\gamma P_{d_*}]v_{\#}$

$\implies r_{d_*} \ge [I-\gamma P_{d_*}]v_{\#}$

$\implies r_{d_*} + \gamma P_{d_*}v_{\#} \ge v_{\#}$

$\implies r_{d_*} + \gamma P_{d_*}v_{\#} \ge r_{d_\#} + \gamma P_{d_\#}v_\#$

W związku z tym iteracja zasad nie kończy się na lokalnym optimum