Jaka jest różnica między iteracją wartości a iteracją polityki?

94

Jaka jest różnica między iteracją polityki a iteracją wartości w uczeniu się przez wzmacnianie ?

O ile rozumiem, w iteracji wartości używasz równania Bellmana do rozwiązania optymalnej polityki, podczas gdy w iteracji polityki wybierasz losowo politykę π i znajdujesz nagrodę za tę politykę.

Wątpię, że jeśli wybierasz losową polisę π w PI, w jaki sposób gwarantuje się, że będzie to optymalna polityka, nawet jeśli wybieramy kilka przypadkowych polis.

Arslán
źródło
13
Bardziej stosowne byłoby zadanie tego pytania na stronach internetowych, takich jak ai.stackexchange.com , stats.stackexchange.com lub datascience.stackexchange.com .
nbro

Odpowiedzi:

124

Przyjrzyjmy się im obok siebie. Podkreślono kluczowe części do porównania. Liczby pochodzą z książki Suttona i Barto: Reinforcement Learning: An Introduction .

wprowadź opis obrazu tutaj Kluczowe punkty:

  1. Iteracja polityki obejmuje: ocenę polityki + poprawę polityki , a obie te czynności są powtarzane aż do zbieżności polityki.
  2. Iteracja wartości obejmuje: znajdowanie funkcji optymalnej wartości + ekstrakcja jednej polityki . Nie ma powtórzenia tych dwóch, ponieważ gdy funkcja wartości jest optymalna, wówczas polityka wychodząca z niej powinna być również optymalna (tj. Zbieżna).
  3. Znalezienie funkcji o optymalnej wartości można również postrzegać jako połączenie ulepszenia polityki (ze względu na maksimum) i skróconej oceny polityki (ponowne przypisanie v_ (s) po zaledwie jednym przejrzeniu wszystkich stanów niezależnie od zbieżności).
  4. Algorytmy oceny zasad i znajdowania funkcji wartości optymalnej są bardzo podobne, z wyjątkiem operacji maksymalnej (jak podkreślono)
  5. Podobnie kluczowy krok w kierunku poprawy polityki i ekstrakcji polityki jest identyczny, z wyjątkiem tego, że pierwszy obejmuje kontrolę stabilności.

Z mojego doświadczenia wynika, że iteracja polityki jest szybsza niż iteracja wartości , ponieważ polityka konwerguje szybciej niż funkcja wartości. Pamiętam, że jest to również opisane w książce.

Wydaje mi się, że zamieszanie wynikało głównie z tych wszystkich nieco podobnych terminów, które również mnie wcześniej myliły.

zyxue
źródło
3
Zgadzam się, że iteracja polityki zbiega się w mniejszej liczbie iteracji, a także przeczytałem w kilku miejscach, że jest szybsza. Zrobiłem kilka prostych eksperymentów z rozwiązywaniem świata pudełkowego i labiryntu obiema metodami w Burlap. Okazało się, że iteracja wartości wykonywała więcej iteracji, ale osiągnięcie zbieżności zajęło mniej czasu. YMMV.
Ryan
1
@Chrom, powinieneś był przeczytać na odwrocie. Oto cytat z książki: „ Iteracja polityki często zbiega się w zaskakująco niewielu iteracjach. Ilustruje to przykład na rysunku 4.1. ”, Ze strony 65 wersji książki 2017nov5 .
zyxue
3
Tak, grałem w kilka odmian świata Grid. Chciałem tylko zaznaczyć, że „Szybsze” pod względem iteracji prawdopodobnie będzie faworyzować PI. Ale „Szybszy” pod względem sekund może w rzeczywistości sprzyjać VI.
Ryan
3
Aby wyjaśnić, iteracja polityki zajmie mniej iteracji, ale jest bardziej złożona obliczeniowo niż iteracja wartości; który jest szybszy, zależy od środowiska.
RF Nelson
2
Wiem, że to stary post. Ale bardzo sugeruję, aby przyjrzeć się temu ( medium.com/@m.alzantot/ ... ) Link zawiera kod, który sprawił, że stał się on dla mnie znacznie bardziej zrozumiały.
tandem
73

W algorytmach iteracji polityki zaczynasz od losowej polityki, następnie znajdujesz funkcję wartości tej polityki (krok oceny polityki), następnie znajdujesz nową (ulepszoną) politykę opartą na poprzedniej funkcji wartości i tak dalej. W tym procesie każda polityka gwarantuje ścisłe ulepszenie w stosunku do poprzedniej (chyba że jest już optymalna). Biorąc pod uwagę zasadę, jej funkcję wartości można uzyskać za pomocą operatora Bellmana .

W iteracji wartości zaczynasz od funkcji wartości losowej, a następnie znajdujesz nową (ulepszoną) funkcję wartości w procesie iteracyjnym, aż do osiągnięcia funkcji wartości optymalnej. Zauważ, że możesz łatwo wyprowadzić optymalną politykę z funkcji optymalnej wartości. Proces ten oparty jest na optymalności operatora Bellmana .

W pewnym sensie oba algorytmy mają tę samą zasadę działania i można je postrzegać jako dwa przypadki uogólnionej iteracji polityki . Jednak operator Bellmana optymalności zawiera operator max , który jest nieliniowy i dlatego ma różne cechy. Ponadto możliwe jest użycie metod hybrydowych między iteracją czystej wartości a iteracją czystej polityki.

Pablo EM
źródło
1
Ładny opis tego. Pozwólcie, że dodam to w iteracji polityki, która używa równania Belmana oczekiwanego, aw iteracji wartości używa równania maksimum Melmana. W przypadku iteracji wartości może to być mniej iteracji, ale dla jednej iteracji może być tak dużo pracy. Dla iteracji polityki więcej iteracji
Shamane Siriwardhana
czy nie ma również operatora max w iteracji zasad? w przeciwnym razie jak zaktualizować zasady na podstawie nowej funkcji wartości?
huangzonghao
Nie, algorytm SARSA jest typowym przykładem iteracji polityki. Jak widać w tym pseudokodzie ( incompleteideas.net/book/ebook/node64.html ), aktualizacja funkcji wartości nie zawiera żadnego operatora max. Jeśli jednak masz na myśli operatora max do wybierania najlepszych działań z funkcji wartości (czyli zachłannych działań), to tak, w takim procesie jest operacja max.
Pablo EM
11

Podstawowa różnica to -

W iteracji zasad - losowo wybierasz politykę i znajdujesz odpowiadającą jej funkcję wartości, a następnie znajdujesz nową (ulepszoną) politykę opartą na poprzedniej funkcji wartości, i tak dalej prowadzi to do optymalnej polityki.

W iteracji wartości - losowo wybierasz funkcję wartości, a następnie znajdujesz nową (ulepszoną) funkcję wartości w procesie iteracyjnym, aż do osiągnięcia funkcji wartości optymalnej, a następnie wyprowadzasz optymalną politykę z tej funkcji wartości optymalnej.

Iteracja polityki działa na zasadzie „Ocena polityki —-> Poprawa polityki”.

Iteracja wartości działa na zasadzie „Optymalna funkcja wartości —-> optymalna polityka”.

Himanshu Gupta
źródło
0

Jeśli o mnie chodzi, w przeciwieństwie do pomysłu @zyxue, VI jest generalnie dużo szybszy niż PI.

Powód jest bardzo prosty, jak już wiesz, równanie Bellmana służy do rozwiązywania funkcji wartości dla danej polityki. Ponieważ możemy rozwiązać funkcję wartości dla optymalnej polityki bezpośrednio , funkcja rozwiązywanie wartość dla bieżącej polityki jest oczywiście strata czasu.

Jeśli chodzi o twoje pytanie o zbieżność PI, myślę, że możesz przeoczyć fakt, że poprawiając strategię dla każdego stanu informacyjnego, ulepszasz strategię dla całej gry. Jest to również łatwe do udowodnienia, jeśli znasz alternatywne minimalizowanie żalu - suma żalu za każdy stan informacji stanowi górną granicę ogólnego żalu, a zatem minimalizacja żalu dla każdego stanu zminimalizuje ogólny żal, który prowadzi do optymalnej polityki.

Odpowiedź777
źródło