Dlaczego stopa dyskontowa w algorytmie REINFORCE pojawia się dwukrotnie?

11

Czytałem książkę Reinforcement Learning: An Introduction autorstwa Richarda S. Sutton i Andrew G. Barto (kompletny szkic, 5 listopada 2017 r.).

Na stronie 271 przedstawiono pseudo-kod dla epizodycznej metody Monte-Carlo z zastosowaniem gradientowej polityki. Patrząc na ten pseudo-kod, nie rozumiem, dlaczego wydaje się, że stopa dyskontowa pojawia się 2 razy, raz w stanie aktualizacji i drugi raz w ramach zwrotu. [Zobacz rysunek poniżej]

wprowadź opis zdjęcia tutaj

Wydaje się, że powrót do kroków po kroku 1 jest jedynie skrótem zwrotu pierwszego kroku. Ponadto, jeśli spojrzysz tylko na jedną stronę powyżej w książce, znajdziesz równanie z tylko 1 stopą dyskontową (tą wewnątrz zwrotu).

Dlaczego zatem pseudo-kod wydaje się inny? Domyślam się, że coś źle rozumiem:

(13.6)θt+1 =˙ θt+αGtθπ(At|St,θt)π(At|St,θt).

Diego Orellana
źródło

Odpowiedzi:

5

Współczynnik rabatu pojawia się dwukrotnie i jest to poprawne.

Wynika to z faktu, że funkcją, którą próbujesz zmaksymalizować w REINFORCE dla problemu epizodycznego (poprzez wzięcie gradientu), jest oczekiwany zwrot z danego (początkowego) rozkładu stanu początkowego:

J(θ)=Eπ(θ)[Gt|St=s0,t=0]

Dlatego podczas odcinka, kiedy próbujesz zwrotów , G 2G1G2 itd., Będą one mniej związane z rozwiązywanym przez ciebie problemem, zmniejszone o współczynnik rabatu po raz drugi, jak zauważyłeś. W skrajnym przypadku z epizodycznym problemem i REINFORCE znajdzie tylko optymalną politykę dla pierwszego działania.γ=0

Inne algorytmy, które działają w ciągłych problemach, takie jak aktor-krytyk, używają różnych sformułowań dla , więc nie mają tego współczynnikaJ(θ) .γt

Neil Slater
źródło
5

Odpowiedź Neila zapewnia już pewną intuicję, dlaczego pseudokod (z dodatkowym terminem ) jest poprawny.γt

Chciałbym tylko dodatkowo wyjaśnić, że wydaje się, że niczego nie rozumiecie , równanie (13.6) w książce rzeczywiście różni się od pseudokodu .

Teraz nie mam wydania książki, o której tu wspomniałeś, ale mam późniejszy szkic z 22 marca 2018 r., A tekst na ten temat wydaje się podobny. W tej edycji:

  • Pod koniec strony 326 wyraźnie wspomniano, że przyjmą γ=1 w dowodzie dla twierdzenia o gradiencie polityki.
  • Dowód ten ostatecznie prowadzi do tego samego równania (13.6) na stronie 329.
  • Bezpośrednio pod pseudokodem, na stronie 330, faktycznie krótko omawiają różnicę między równaniem a pseudokodem, mówiąc, że różnica ta wynika z założenia γ=1 w dowodzie.
  • Poniżej w ćwiczeniu 13.2 podają pewne wskazówki, na co powinieneś zwrócić uwagę, jeśli chcesz uzyskać zmodyfikowany dowód na wypadek, gdy .γ<1
Dennis Soemers
źródło
2
Dzięki. W projekcie z 2017 r. Brakowało wyjaśnienia trzeciego punktu.
Diego Orellana,
2
@DiegoOrellana Nie mogę już znaleźć linku do szkicu z 22 marca, wydaje się, że istnieje jeszcze późniejszy szkic (nie mogę znaleźć wspomnianej daty) tutaj . Ta wersja faktycznie ma fantazyjną okładkę, więc może nawet być wersją ostateczną, a nie szkicową. Jeśli link się zepsuje w przyszłości, podejrzewam, że nowy link zostanie udostępniony tutaj .
Dennis Soemers
3

To subtelna kwestia.

Jeśli spojrzysz na algorytm A3C w oryginalnym artykule (p.4 i dodatek S3 dla pseudokodu), ich algorytm krytykujący aktora (ten sam algorytm, zarówno problemy epizodyczne, jak i ciągłe) jest wyłączony przez współczynnik gamma względem aktora krytyk pseudokod dotyczący problemów epizodycznych w książce Sutton i Barto (s.332 wydanie ze stycznia 2019 r. http://incompleteideas.net/book/the-book.html ). Książka Sutton i Barto ma dodatkową „pierwszą” gamma oznaczoną na zdjęciu. Więc książka lub papier A3C jest w błędzie? Nie całkiem.

Klucz znajduje się na str. 199 książki Sutton and Barto:

Jeżeli występuje dyskontowanie (gamma <1), powinno to być traktowane jako forma wypowiedzenia, co można zrobić po prostu poprzez uwzględnienie współczynnika w drugim okresie (9.2).

Subtelną kwestią jest to, że istnieją dwie interpretacje współczynnika dyskontowego gamma:

  1. Współczynnik mnożnikowy, który kładzie mniejszy nacisk na odległe przyszłe nagrody.
  2. Prawdopodobieństwo 1 - gamma, że ​​symulowana trajektoria fałszywie kończy się w dowolnym momencie. Ta interpretacja ma sens tylko w przypadkach epizodycznych, a nie w przypadku kontynuacji.

Dosłowne realizacje:

  1. Po prostu pomnóż przyszłe nagrody i związane z nimi ilości (V lub Q) w przyszłości przez gamma.
  2. Symuluj niektóre trajektorie i losowo kończ je (1 - gamma) na każdym kroku. Przerwane trajektorie nie dają natychmiastowych ani przyszłych nagród.

Glnπ(a|s) z drugą interpretacją.

γ2Glnπ(a|s)0.81Glnπ(a|s) . Ten warunek ma o 19% mniejszą moc gradientu niż warunek t = 0 z tego prostego powodu, że 19% symulowanych trajektorii zanikło o t = 2.

Glnπ(a|s)G

Możesz wybrać dowolną interpretację gamma, ale musisz pamiętać o konsekwencjach dla algorytmu. Osobiście wolę trzymać się interpretacji 1 tylko dlatego, że jest prostsza. Używam więc algorytmu w papierze A3C, a nie w książce Sutton i Barto.

Twoje pytanie dotyczyło algorytmu REINFORCE, ale dyskutowałem o aktorach-krytykach. Masz dokładnie ten sam problem związany z dwiema interpretacjami gamma i dodatkową gamma w REINFORCE.

toto2
źródło