Problem Warrena Buffetta

Oto streszczenie problemu nauki online / bandyty, nad którym pracowałem latem. Nie widziałem wcześniej takiego problemu i wygląda całkiem interesująco. Jeśli znasz jakieś powiązane prace, byłbym wdzięczny za referencje.

Problem Ustawienie dotyczy wielorękich bandytów. Masz N. broni. Każde ramię ma nieznany, ale stały rozkład prawdopodobieństwa nad nagrodami, które można zdobyć, grając w niego. Dla konkretności załóżmy, że każde ramię i płaci nagrodę 10 $ z prawdopodobieństwem p [i] i nagrodę 0 $ z prob. 1-p [i] .

W każdej rundzie t wybierasz zestaw S [t] broni do gry. Za każde wybrane ramię płacisz z góry 1 USD . Za każdą wybraną rękę zbierasz nagrodę pochodzącą z (nieznanego) rozkładu prawdopodobieństwa nagrody tej ręki. Wszystkie nagrody są dodawane na twoje konto bankowe, a wszystkie opłaty są odejmowane od tego konta. Ponadto otrzymasz kredyt w wysokości 1 USD na początku każdej iteracji.

Problem polega na opracowaniu polityki wyboru podzbioru uzbrojenia do gry w każdej iteracji, aby zmaksymalizować zysk (tj. Nagrody minus opłaty za grę) w wystarczająco długim horyzoncie czasowym, z zastrzeżeniem, że musi on utrzymywać nieujemny bilans konta na poziomie cały czas.

Nie określiłem, czy dystrybucje nagród na ramię są wybierane z wcześniejszej dystrybucji, czy wybierane przez przeciwnika. Oba wybory mają sens. Sformułowanie przeciwnika jest dla mnie bardziej atrakcyjne, ale prawdopodobnie trudniejsze do zrobienia. Tutaj przeciwnik wybiera wektor (D1, D2, .., DN) rozkładów. Biorąc pod uwagę wypłaty, optymalną polityką zrównoważoną budżetowo jest gra wszystkimi broniami, których oczekiwana nagroda jest większa niż 1 $. Niech P będzie zyskiem na krok tej optymalnej wszechwiedzącej polityki. Chcę, aby moje zasady online minimalizowały żal (tj. Utratę zysków w przedziale czasu T) w stosunku do tej wszechwiedzącej zasady.

machine-learning lg.learning online-learning

— Martin Pál
źródło

Czy jesteś pewien, że najlepszą strategią jest gra wszystkimi ramionami, których oczekiwana nagroda jest większa niż 1 $ w każdej rundzie? Jeśli masz ścisłe ograniczenie, że musisz utrzymywać nieujemne saldo konta przez cały czas, mogą istnieć rundy, w których nawet nie możesz grać.

— Matthias

Więc nie znasz prawdopodobieństwa nagrody, ale możesz określić wypłatę z każdego ramienia?

— David Thornley,

Nie znasz prawdopodobieństwa i nie znasz oczekiwanych nagród. Wszechwiedząca „optymalna” polityka, z którą chcę się porównać, może jednak grać wszystkimi ramionami z nagrodą większą niż 1, ponieważ jest wszechwiedząca.

— Martin Pál

Zaryzykuję, że po rundach

można uzyskać oczekiwany dochód w stałym współczynniku optymalnym, po którym problem wydaje się stracić większość swojego niezwykłego charakteru. Dolna granica

wynika z przypadku, w którym tylko jedno ramię ma niezerową wypłatę. Nie widzę od razu górnej granicy.

Θ (N)

$\Theta(N)$

Ω (N)

$\Omega(N)$

— Warren Schudy,

Korekta: po rundach

prawdopodobnie nie możesz zagwarantować osiągnięcia stałego współczynnika optymalnego dochodu. Prawdopodobnie możesz jednak uzyskać tę gwarancję w stosunku do dochodu dostępnego z broni, która spodziewała się zwrotu co najmniej 2 dolary.

Θ (N)

$\Theta(N)$

— Warren Schudy,

Wyobrażam sobie, że istnieje wiele możliwych podejść do tego problemu (z których wiele jestem pewien, że wziąłeś pod uwagę) - oto kilka pomysłów / referencji.

Możesz grać w to jako niezależne niezależne jednorękie bandyty, decydując się pociągnąć lub nie pociągnąć oddzielnie każdego ramienia. Powinno to działać szczególnie dobrze, jeśli nagrody są rozdzielane niezależnie. $N$
Pozwól, aby każdy zestaw ramion był nowym uzbrojeniem i uruchom algorytm typu Exp3. Daje to żal - nie jest tak wielkie. $O(2^{N/2} T^{1/2})$
W nadchodzącym artykule NIPS 2010 Saten Kale, Rob Schapire i ja rozważam przypadek, w którym gra się jednocześnie w tablicę broni. Jednak w naszej pracy rozmiar łupka jest stały. W tym dokumencie rozważany jest również podobny problem. Kolejna podobna praca pojawiła się w ALT 2010. Być może niektóre pomysły zostały przekazane.
$2^N$ $O(N\sqrt{T})$ $O(2^N T)$

EDYTUJ poniżej:

$0$ $1$ $(n-1)/n$ $T$ $T$ $(n-1)T/n$

$B$ $0$ $2B$ $1/B$

— Lew Reyzin
źródło

Cześć Lev, dzięki za wskazówki. Zgadzam się, że gdybym miał nieograniczony początkowy budżet, granie w N równoległych jednorękich bandytów rozwiązałoby problem. Ograniczenie budżetowe wprowadza jednak sprzężenie między bronią i czyni sprawy interesującymi. W szczególności na pierwszym etapie masz budżet tylko na jedną rękę. W drugim kroku możesz zagrać 11 lub tylko 1 ramię, w zależności od tego, czy masz szczęście w pierwszym kroku i tak dalej. Dlatego ważne jest, aby wcześnie znaleźć garść dochodowych broni, a następnie skorzystać z dalszej eksploracji.

— Martin Pál

Nie zdawałem sobie sprawy, że był początkowy budżet (teraz rozumiem część dotyczącą „nieujemnego salda”, ale być może można to wyjaśnić w pytaniu?) - dzięki temu problem jest bardziej interesujący. Przyjemna może być również wersja „kontekstowa” lub wersja dla ekspertów. Niestety nie znam żadnych bardziej odpowiednich odniesień do tego problemu.

— Lev Reyzin

Jeśli dobrze rozwiążę problem, zyskujesz dodatkowo 1 USD w każdej rundzie. Martin, czy mógłbyś wyjaśnić pytanie?

— Jukka Suomela

Myślę, że zyskujesz cokolwiek, co zapłaci maszyna, jeśli grasz w nią i wygrywasz i przegrywasz 1 $, ilekroć zdecydujesz się na grę.

— Lew Reyzin