Zrozumienie roli czynnika dyskontowego w uczeniu się wzmacniającym

43

Uczę się o uczeniu się przez wzmocnienie i staram się zrozumieć koncepcję nagrody dyskontowej. Zatem nagroda jest konieczna, aby powiedzieć systemowi, które pary stan-działanie są dobre, a które złe. Ale nie rozumiem, dlaczego zniżka jest konieczna. Dlaczego miałoby mieć znaczenie, czy dobry stan zostanie osiągnięty wkrótce, czy później?

Rozumiem, że jest to istotne w niektórych szczególnych przypadkach. Na przykład, jeśli korzystasz z nauki o wzmocnieniu, aby handlować na giełdzie, bardziej korzystne jest uzyskanie zysku wcześniej niż później. Dzieje się tak, ponieważ posiadanie tych pieniędzy pozwala teraz robić rzeczy z tymi pieniędzmi teraz, co jest bardziej pożądane niż robienie rzeczy z tymi pieniędzmi później.

Ale w większości przypadków nie rozumiem, dlaczego udzielanie rabatów jest przydatne. Załóżmy na przykład, że chciałeś, aby robot nauczył się poruszać po pokoju, aby przejść na drugą stronę, gdzie grożą kary, jeśli zderzy się z przeszkodą. Gdyby nie było żadnego współczynnika rabatu, to nauczyłby się idealnie docierać na drugą stronę, bez kolizji z żadnymi przeszkodami. Dotarcie tam może zająć dużo czasu, ale w końcu się tam dostanie.

Ale jeśli udzielimy zniżki na nagrodę, wówczas robot będzie zachęcany do szybkiego przejścia na drugą stronę pokoju, nawet jeśli po drodze zderzy się z obiektami. To zdecydowanie nie jest pożądany wynik. Jasne, że chcesz, aby robot szybko przeszedł na drugą stronę, ale nie, jeśli oznacza to, że po drodze musi zderzyć się z obiektami.

Mam więc intuicję, że każda forma współczynnika rabatu faktycznie doprowadzi do rozwiązania nieoptymalnego. A wybór współczynnika dyskonta często wydaje się arbitralny - wiele metod, które widziałem, po prostu ustawia go na 0,9. Wydaje mi się to bardzo naiwne i wydaje się dawać arbitralny kompromis między rozwiązaniem optymalnym a najszybszym, podczas gdy w rzeczywistości ten kompromis jest bardzo ważny.

Proszę, czy ktoś może mi pomóc to wszystko zrozumieć? Dziękuję Ci :)

Karnivaurus
źródło

Odpowiedzi:

36

TL; DR.

Fakt, że stopa dyskontowa musi być mniejsza niż 1, jest matematyczną sztuczką pozwalającą na skończenie nieskończonej sumy. Pomaga to udowodnić zbieżność niektórych algorytmów.

W praktyce współczynnik dyskonta można wykorzystać do modelowania faktu, że osoba podejmująca decyzję nie jest pewna, czy w następnej chwili decyzji świat (np. Środowisko / gra / proces ) się skończy.

Na przykład:

Jeśli decydentem jest robot, czynnikiem dyskontowym może być prawdopodobieństwo, że robot zostanie wyłączony w następnej chwili (świat kończy się na poprzedniej terminologii). To jest powód, dla którego robot jest krótkowzroczny i nie optymalizuje nagrody ogólnej, ale nagrodę zdyskontowaną .

Współczynnik rabatu mniejszy niż 1 (szczegółowo)

Aby precyzyjniej odpowiedzieć, dlaczego stopa dyskontowa musi być mniejsza niż jedna, najpierw przedstawię procesy decyzyjne Markowa (MDP).

Techniki uczenia się przez wzmocnienie mogą być stosowane do rozwiązywania MDP. MDP zapewnia ramy matematyczne do modelowania sytuacji decyzyjnych, w których wyniki są częściowo losowe, a częściowo pod kontrolą decydenta. MDP jest definiowany za pomocą przestrzeni stanów , przestrzeni akcji , funkcji prawdopodobieństwa przejścia między stanami (uwarunkowanej działaniem podejmowanym przez decydenta) oraz funkcji nagrody.SA

W swoim podstawowym ustawieniu podejmujący decyzję podejmuje działania i otrzymuje nagrodę od środowiska, a środowisko zmienia swój stan. Następnie decydent wyczuwa stan środowiska, podejmuje działania, otrzymuje nagrodę i tak dalej. Przejścia stanu są probabilistyczne i zależą wyłącznie od stanu faktycznego i działań podejmowanych przez decydenta. Nagroda uzyskana przez osobę podejmującą decyzję zależy od podjętych działań oraz zarówno od pierwotnego, jak i nowego stanu środowiska.

Nagroda jest uzyskiwana przy podejmowaniu działania w stanie a środowisko / system zmienia się w stan po tym, jak podejmujący decyzję podejmie działanie . Decydent postępuje zgodnie z polityką , że dla każdego stanu podejmuje działanie . Tak więc polityka mówi decydentowi, jakie działania podjąć w każdym stanie. Polityka może być randomizowane jak dobrze, ale to nie ma znaczenia teraz.Rai(sj,sk)aisjskaiπ π():SAsjSaiAπ

Celem jest znalezienie politycznego taki, żeπ

maxπ:S(n)ailimTE{n=1TβnRxi(S(n),S(n+1))}(1),
gdzie jest współczynnikiem dyskontowym, a .ββ<1

Zauważ, że powyższy problem optymalizacji ma nieskończony horyzont czasowy ( ), a celem jest maksymalizacja sumy nagrody (nagroda jest pomnożona przez ). Zwykle jest to nazywane problemem MDP z kryteriami nagrody z nieskończonym horyzontem .TdiscountedRβn

Problem nazywa się dyskontem, ponieważ . Gdyby nie był to dyskontowany problem suma nie byłaby zbieżna. Wszystkie polisy, które za każdym razem otrzymują średnio pozytywną nagrodę, sumują się do nieskończoności. Byłoby to kryterium nagrody o nieskończonym horyzoncie i nie jest dobrym kryterium optymalizacji.β<1β=1

Oto zabawkowy przykład pokazujący, co mam na myśli:

Załóżmy, że są tylko dwie możliwe akcje i że funkcja nagrody jest równa jeśli , i jeśli (nagroda nie zależy od stanu).a=0,1R1a=10a=0

Oczywistym jest, że polityka, która otrzymuje więcej nagród, polega na podejmowaniu zawsze akcji i nigdy akcji . Zadzwonię do tej zasady . Porównuję z inną polityką która podejmuje działanie z małym prawdopodobieństwem , a działanie przeciwnym razie.a=1a=0πππa=1α<<1a=0

W nieskończonym horyzoncie zdyskontowane kryteria nagrody równanie (1) staje się (suma szeregu geometrycznego) dla polisy podczas gdy dla polisy równanie (1) staje się . Ponieważ mówimy, że jest lepszą polityką niż . W rzeczywistości jest optymalną polityką.11βππα1β11β>α1βπππ

W nieskończonym horyzoncie kryteria nagrody ( ) równanie (1) nie jest zbieżne dla żadnej z zasad (sumuje się do nieskończoności). Tak więc, podczas gdy zasady osiągają wyższe nagrody niż obie zasady są równe zgodnie z tymi kryteriami. To jeden z powodów, dla których kryteria nagrody nieskończonej sumy horyzontu nie są przydatne.β=1ππ

Jak wspomniałem wcześniej, sprawia, że ​​sztuczka polega na zbieraniu sumy w równaniu (1).β<1

Inne kryteria optymalizacji

Istnieją inne kryteria optymalizacji, które nie narzucają, że :β<1

Przypadek kryterium skończonego horyzontu, gdy celem jest maksymalizacja zdyskontowanej nagrody do czasu, gdy horyzont czasowyT

maxπ:S(n)aiE{n=1TβnRxi(S(n),S(n+1))},

dla i skończony.β1T

W kryteriach średniej nagrody nieskończonego horyzontu celem jest

maxπ:S(n)ailimTE{n=1T1TRxi(S(n),S(n+1))},

Uwaga końcowa

W zależności od kryteriów optymalizacyjnych do znalezienia optymalnej polityki można użyć innego algorytmu. Na przykład optymalna polityka problemów z skończonym horyzontem zależałaby zarówno od stanu, jak i od rzeczywistego momentu. Większość algorytmów uczenia się zbrojenia (takich jak SARSA lub Q-learning) jest zbieżna z optymalną polityką tylko w przypadku kryteriów zdyskontowanych nagród o nieskończonym horyzoncie (to samo dzieje się w przypadku algorytmów programowania dynamicznego). W przypadku kryteriów średniej nagrody nie wykazano, że algorytm jest zbieżny z optymalną polityką, jednak można zastosować R-learning, który ma dobrą wydajność, choć nie jest to dobra zbieżność teoretyczna.

PolBM
źródło
1
Masz pomysł na to, co powinienem przeczytać, aby zrozumieć wszystkich Chińczyków w swojej odpowiedzi?
thibaut noah
@thibautnoah To jest najlepsza referencja IMHO Reinforcement Learning: Wprowadzenie Sutton i Barto. [ people.inf.elte.hu/lorincz/Files/RL_2006/SuttonBook.pdf]
PolBM
dzięki kolego, prawdopodobnie potrzebuję kolejnej książki o matematyce, ale myślę, że to początek;)
Thibaut noah
6

Masz rację, że współczynnik dyskontowy (tzw. - zwróć uwagę, że różni się on od od TD- ) działa jak „pilna potrzeba życia” i dlatego stanowi część problemu - tak jak jest ludzkie życie: Niektórzy ludzie żyją tak, jakby żyli wiecznie; niektórzy ludzie żyją tak, jakby mieli umrzeć jutro.γλλ

Neil G.
źródło
2

TL; DR: Czynniki dyskontowe są powiązane z horyzontami czasowymi. Dłuższe horyzonty czasowe mają znacznie większą zmienność, ponieważ zawierają więcej nieistotnych informacji, natomiast krótkie horyzonty czasowe są ukierunkowane jedynie na zyski krótkoterminowe.

Współczynnik rabatu zasadniczo określa, jak bardzo agenci uczący się o wzmocnienie dbają o nagrody w odległej przyszłości w porównaniu z nagrodami w najbliższej przyszłości. Jeśli , agent będzie całkowicie krótkowzroczny i dowie się tylko o działaniach, które dają natychmiastową nagrodę. Jeśli , agent oceni każde swoje działanie na podstawie sumy wszystkich swoich przyszłych nagród.γ=0γ=1

Dlaczego więc nie zawsze chciałbyś ustawić tak wysoko, jak to możliwe? Cóż, większość działań nie ma długotrwałych następstw. Załóżmy na przykład, że pierwszego dnia każdego miesiąca decydujesz się na koktajl i musisz zdecydować, czy dostaniesz koktajl jagodowy czy truskawkowy. Jako dobry uczeń wzmacniający, oceniasz jakość swojej decyzji na podstawie tego, jak duże są twoje kolejne nagrody. Jeśli twój horyzont czasowy jest bardzo krótki, weźmiesz pod uwagę tylko natychmiastowe nagrody, takie jak to, jak smaczny jest twój koktajl. Przy dłuższym horyzoncie czasowym, takim jak kilka godzin, możesz również wziąć pod uwagę takie czynniki, jak to, czy masz rozstrój żołądka. Ale jeśli twój horyzont czasowy trwa przez cały miesiąc, to każda rzecz, która sprawia, że ​​czujesz się dobrze lub źle przez cały miesiącγweźmie pod uwagę, czy podjąłeś właściwą decyzję dotyczącą koktajlu. Będziesz uwzględniał wiele nieistotnych informacji, a zatem twój osąd będzie miał wielką wariancję i trudno będzie się go nauczyć.

Wybór określonej wartości jest równoznaczny z wybraniem horyzontu czasowego. Pomaga przepisać nagrodę agenta jako gdzie identyfikuję i . Wartość wyraźnie pokazuje horyzont czasowy związany z czynnikiem dyskontowym; odpowiada , a wszelkie nagrody, które są znacznie większe niżγG

Gt=Rt+γRt+1+γ2Rt+2+=k=0γkRt+k=Δt=0eΔt/τRt+Δt
γ=e1/τkΔtτγ=1τ=τstopnie czasu w przyszłości są wykładniczo tłumione. Zasadniczo powinieneś wybrać współczynnik rabatu, aby horyzont czasowy zawierał wszystkie odpowiednie nagrody za dane działanie, ale już nie.

clwainwright
źródło