Czy optymalna polityka jest zawsze stochastyczna, jeśli środowisko jest również stochastyczne?

Czy optymalna polityka jest zawsze stochastyczna (tj. Mapa stanów do rozkładu prawdopodobieństwa na działania), jeśli środowisko jest również stochastyczne?

Intuicyjnie, jeśli środowisko jest deterministyczne (to znaczy, jeśli agent jest w stanie $s$ i podejmuje działanie , wtedy następny stan jest zawsze taki sam, bez względu na krok czasowy, wtedy optymalna polityka powinna być również deterministyczna (to znaczy powinna być mapą stanów do działań, a nie prawdopodobieństwa podział na działania). $a$ $s'$

— nbro
źródło

Oto powiązane pytanie: mathoverflow.net/q/44677 .

— nbro

Odpowiedzi:

Czy optymalna polityka jest zawsze stochastyczna (tj. Mapa stanów do rozkładu prawdopodobieństwa na działania), jeśli środowisko jest również stochastyczne?

Nie.

Optymalna polityka jest zasadniczo deterministyczna, chyba że:

Brakuje ważnych informacji o stanie (POMDP). Na przykład na mapie, na której agent nie może znać swojej dokładnej lokalizacji ani pamiętać poprzednich stanów, a podany stan nie wystarcza do rozróżnienia między lokalizacjami. Jeśli celem jest dotarcie do określonej lokalizacji końcowej, optymalna polityka może obejmować losowe ruchy, aby uniknąć utknięcia. Zauważ, że środowisko w tym przypadku może być deterministyczne (z perspektywy kogoś, kto widzi cały stan), ale nadal może prowadzić do stochastycznej polityki, aby go rozwiązać.
Istnieje pewien scenariusz teorii gier minimax, w którym polityka deterministyczna może zostać ukarana przez środowisko lub innego agenta. Pomyśl o nożyczkach / papierze / kamieniu lub dylemacie więźnia.

Intuicyjnie, jeśli środowisko jest deterministyczne (to znaczy, jeśli agent jest w stanie 𝑠 i podejmuje działanie 𝑎, to następny stan 𝑠 ′ jest zawsze taki sam, bez względu na krok), wówczas optymalna polityka powinna być również deterministyczna (to znaczy powinna to być mapa stanów do akcji, a nie rozkład prawdopodobieństwa na akcje).

Wydaje się to rozsądne, ale tę intuicję możesz posunąć dalej za pomocą dowolnej metody opartej na funkcji wartości:

Jeśli znalazłeś optymalną funkcję wartości, to zachłanność w stosunku do niej jest optymalną polityką.

Powyższe stwierdzenie jest tylko naturalnym wyrażeniem równania optymalności Bellmana:

v^{*} (s) = {max}_{za} \sum_{r, s^{'}} p (r, s^{'} | s, za) (r + γ v^{*} (s^{'}))

$v^*(s) = \text{max}_a \sum_{r,s'}p(r,s'|s,a)(r+\gamma v^*(s'))$

tzn. optymalne wartości są uzyskiwane zawsze przy wyborze akcji, która maksymalizuje nagrodę plus zdyskontowana wartość następnego kroku. The $\text{max}_a$ operacja jest deterministyczna (w razie potrzeby można zerwać powiązania dla wartości maksymalnej deterministycznie np. z uporządkowaną listą akcji).

Dlatego każde środowisko, które można modelować za pomocą MDP i rozwiązywać metodą opartą na wartościach (np. Iteracja wartości, Q-learning), ma optymalną politykę deterministyczną.

Jest możliwe w takim środowisku, że optymalne rozwiązanie może wcale nie być stochastyczne (tj. Jeśli dodasz dowolność do deterministycznej optymalnej polityki, polityka stanie się zdecydowanie gorsza). Jeśli jednak istnieją powiązania dla maksymalnej wartości dla jednego lub większej liczby działań w jednym lub większej liczbie stanów, istnieje wiele równoważnych optymalnych i deterministycznych polityk. Możesz stworzyć strategię stochastyczną, która łączy je w dowolną kombinację, i będzie również optymalna.

— Neil Slater
źródło

„Czy w takim środowisku żadna polityka stochastyczna nie jest optymalna”, masz na myśli politykę deterministyczną?

— nbro

@nbro: Nie, naprawdę mam na myśli, że nie ma optymalnej polityki stochastycznej. Tak jest zwykle. Pomyśl na przykład o prostym rozwiązaniu labiryntu. Jeśli optymalne rozwiązanie deterministyczne stanowi jedną ścieżkę od początku do końca, dodanie do niej jakiejkolwiek losowości spowoduje, że polityka będzie zdecydowanie gorsza. Nie zmienia się to, jeśli środowisko dodaje losowy hałas (np. Ruchy czasami zawodzą)

— Neil Slater

Teraz rozumiem. Mówisz, że zawsze istnieje polityka deterministyczna, wówczas polityka stochastyczna i wywodząca się z polityki deterministycznej prawdopodobnie będzie gorsza niż optymistyczna polityka deterministyczna.

— nbro

@nbro: Tak, to wszystko.

— Neil Slater

Powiedziałbym „nie”.

Rozważmy na przykład problem wielorękiego bandyty . Więc masz $n$ ramiona, które prawdopodobnie dają nagrodę (na przykład 1 punkt), $p_i$ , $i$ będąc między 1 a $n$ . Jest to proste środowisko stochastyczne: jest to środowisko jednopaństwowe, ale nadal jest środowiskiem.

Ale oczywiście optymalną polityką jest wybór ramienia z najwyższym $p_i$ . To nie jest polityka stochastyczna.

Oczywiście, jeśli jesteś w środowisku, w którym grasz przeciwko innemu agentowi (ustawienie teorii gier), twoja optymalna polityka z pewnością będzie stochastyczna (np. Gra w pokera).

— Adrien Forbu
źródło

Dlaczego miałoby być oczywiste, aby zawsze wybierać ramię o najwyższej wartości

p_{i}

$p_i$ ?

p_{i}

$p_i$ jest prawdopodobne, więc nie jest pewne, że zawsze otrzymasz najwyższą kwotę nagrody (przynajmniej w określonym czasie), jeśli zawsze wybierzesz ramię

i

$i$ .

— nbro

@nbro: Pewne jest oczekiwanie, co maksymalizuje optymalna polityka. Zasady nie próbują odgadnąć generatorów liczb losowych, co jest uważane za niemożliwe (jeśli byłoby to możliwe z powodu jakiegoś wewnętrznego stanu systemu, musisz albo dodać ten wewnętrzny stan do modelu, albo traktować jako POMDP)

— Neil Slater

@NeilSlater Ok. Ale czy wniosek zmieniłby się, gdyby czas był skończony? Jeśli masz ograniczoną ilość czasu na grę, to, jak sądzę, oczekiwanie musi również wziąć pod uwagę dostępny czas na grę.

— nbro

@nbro: To może zmienić twoje decyzje, ale tak naprawdę nie chodzi o optymalną politykę. Optymalna polityka zbrojnych bandytów jest nadal deterministyczna, jeśli chodzi o użycie najlepszego ramienia, ale nie wiesz o tym. Chodzi o eksplorację kontra eksploatację. Można by to sformułować jako „optymalną zasadę postępowania z problemem bandyty”. Nie terminologię stosowaną np. W Sutton i Barto, ale być może niektórzy mówcy tak mówią, nie wiem. . .

— Neil Slater

Środowisko zawiera tylko jeden stan, w którym ciągle podejmujesz tę samą decyzję: które ramię muszę wybrać?

— Adrien Forbu

Mam na myśli krajobraz prawdopodobieństwa, w którym znajdziesz się jako aktor, z różnymi nieznanymi szczytami i dolinami. Dobre deterministyczne podejście zawsze może doprowadzić cię do najbliższego lokalnego optimum, ale niekoniecznie do globalnego optimum. Aby znaleźć globalne optimum, coś w rodzaju algorytmu MCMC pozwoliłoby stochastycznie zaakceptować chwilowo gorszy wynik w celu ucieczki od lokalnego optimum i znalezienia globalnego optimum. Moją intuicją jest to, że w stochastycznym środowisku byłoby to również prawdą.

— Jonathan Moore
źródło