Wieloręki bandyta do ogólnej dystrybucji nagród

11

Pracuję nad problemem wielorękiego bandyty, w którym nie mamy żadnych informacji na temat dystrybucji nagród.

Znalazłem wiele artykułów, które gwarantują żal granice dla rozkładu o znanym wiązaniu i dla ogólnych rozkładów ze wsparciem w [0,1].

Chciałbym dowiedzieć się, czy istnieje sposób na dobre wyniki w środowisku, w którym dystrybucja nagród nie ma żadnych gwarancji dotyczących jej wsparcia. Próbuję obliczyć nieparametryczny limit tolerancji i użyć tej liczby do skalowania dystrybucji nagród, aby móc użyć algorytmu 2 określonego w tym dokumencie ( http://jmlr.org/proceedings/papers/v23/agrawal12/agrawal12.pdf ). Czy ktoś myśli, że to podejście zadziała?

Jeśli nie, czy ktoś może wskazać mi właściwe miejsce?

Wielkie dzięki!

references multiarmed-bandit Gość
źródło

Odpowiedzi:

6

Badanie algorytmów MAB jest ściśle powiązane z teoretycznymi gwarancjami wydajności. Rzeczywiście, odrodzenie zainteresowania tymi algorytmami (przypomnijmy, że próbkowanie Thompsona zaproponowano w latach 30.) nastąpiło naprawdę dopiero od czasu, gdy w 2002 r. Praca Auera wykazała, że żałuje granic różnych UCB i -greedy algorytmy. W związku z tym nie ma większego zainteresowania problemami, w których podział nagród nie jest znany, ponieważ prawie nic nie można powiedzieć teoretycznie.O(log⁡(T))ϵ

Nawet prosty algorytm próbkowania Thompsona, o którym wspominasz, wymaga nagród Bernoulliego, a nawet 80 lat zajęło udowodnienie logarytmicznego żalu!

W praktyce jednak w przypadkach, w których na pewno nie znasz rozkładu nagród, możesz po prostu przeskalować go do , dzieląc przez dużą liczbę , a jeśli zauważysz nagrodę powyżej podwoj wartość, . Nie ma jednak gwarancji żałowania przy użyciu tego podejścia, ale zwykle działa całkiem dobrze.[0,1]SSS:=2S

Ponadto wspomniany algorytm próbkowania Thompson wymaga prób Bernoulliego, więc nie można używać dowolnych ciągłych nagród. Możesz zainstalować rozkład Gaussa z tyłu zamiast Beta, ale jest to nieco wrażliwe na twój wybór wcześniejszego, więc możesz chcieć ustawić go tak, aby był bardzo płaski. Jeśli nie chcesz niczego udowadniać na temat swojej implementacji, prawdopodobnie będzie to działać całkiem dobrze.

fairidox
źródło
1
Wielkie dzięki za odpowiedź! Bardzo to doceniam! Miałem jednak pytanie. Myślę, że algorytm 2 na papierze (na górze strony 39.4), o którym wspomniałem, nie wymaga niczego w kwestii podziału nagrody, ALE fakt, że jest on obsługiwany w [0,1]. Może patrzyłeś na algorytm 1?
gość
Tak, fajnie, całkiem interesująca sztuczka, aby przekonwertować rzeczywiste wartości na próbki Bernoulli, dzięki za wskazanie, że szczegóły mi uciekły. W każdym razie, jak mówisz, nadal potrzebujesz zmiennych ograniczonych, możesz to zrobić za pomocą taniej podwójnej sztuczki, o której wspomniałem, i użyć tej wersji próbkowania Thompsona. Ale być może lepiej jest sformułować metodę, która wykorzystuje tylny gaussowski.
fairidox
Przyjrzę się bardziej metodzie tylnej Gaussa, ale co rozumiesz przez „płaski” w kategoriach Gaussa? Zakładam, że wcześniej odpowiada to Beta (1,1) (jednolita), prawda?
gość
prawda, ale oczywiście nie możesz mieć munduru przed nieograniczoną domeną. Tak więc, jeśli masz model Gaussa z tyłu, najprawdopodobniej miałbyś wcześniejszego Gaussa, więc na ogół chcesz, aby był on „płaski” lub pozbawiony informacji, jak to możliwe. Ogólnie oznacza to, że wariancja jest tak duża, jak tylko możesz znieść. Nie jestem ekspertem, ale istnieje cała dziedzina badań nad tym, jak konstruować nieinformacyjne i potencjalnie niewłaściwe priorytety, na które warto przyjrzeć się. Ponadto, jeśli masz ściśle pozytywne nagrody, możesz rozważyć inny model.
fairidox