Jednoręki bandyta to kolokwialna nazwa automatu, który można spotkać w kasynach na całym świecie. Zasady gry są proste: wrzucamy monety, pociągamy za rączkę i czekamy, aż automat się zatrzyma. Jeśli mamy szczęście, wygrywamy więcej, niż wrzuciliśmy. Teraz załóżmy, że mamy do wyboru K automatów – który z nich powinniśmy wybrać? Ten wpis przedstawia propozycję taktyki, która zwiększa nasze szanse wygranej dzięki koncepcjom statystycznym.
Założenia
Żeby utożsamić czytelnika z problemem, wprowadźmy pewien scenariusz.
Mamy paskudny nawyk uprawiania hazardu. Uzależnienie opuści nas dopiero po rozegraniu 1000 gier. Będziemy grać na trzech dostępnych maszynach. Każda maszyna ma stałe, nieznane nam prawdopodobieństwo wygranej (wartość od 0 do 1). Wszystkie pieniądze, które mamy, dostaliśmy od kochanej babci pod choinkę, więc przegrana nawet złotówki jest dla nas bardzo bolesna.
Rozwiązanie zdroworozsądkowe
Co podpowiada nam intuicja? Pewna liczba monet wrzucona do maszyny pozwoli nam oszacować, jak często konkretny jednoręki wygrywa. Po zagospodarowaniu pewnej ilości N dla każdej maszyny otrzymamy wartości:

Rysunek 1. obrazuje wyniki symulacji gier dla różnych wartości N. Odbywając X = 100 sesji po 1000 gier, możemy estymować wartość oczekiwaną zwrotu. Przed każdą z sesji zostały wygenerowane losowe wartości prawdopodobieństwa wygranej każdej z maszyn (z przedziału 0 – 0,5). Obserwujemy duży szum między estymacjami, czego przyczyna tkwi w małej liczbie X symulowanych sesji. Im byłaby ona większa, tym wartość średnia próby bliższa byłaby prawdziwej wartości oczekiwanej. Korzystając z regresji, zakładamy wpływ szumu na uzyskane wartości. Rysunek 1. zawiera dodatkowo wykreślenie modelu (regresja jądrowa z bazową funkcją radialną) dopasowanego do danych. Wskazuje nam przewidywaną wartość zwrotu w zależności od N monet zainwestowanych w każdą z maszyn.

Podejście Bayesowskie
Innym podejściem będzie próba szacowania rozkładów prawdopodobieństwa nad wartościami parametrów. Twierdzenie Bayesa pozwala nam sprecyzować procedurę modyfikacji naszych oczekiwań dotyczących wartości, które mogą przyjmować prawdopodobieństwa wygranej konkretnej maszyny.

Rozkład danych (ponieważ możemy tylko wygrać lub przegrać w pojedynczej grze) ma postać:


Wymnożenie obydwu funkcji i normalizacja sprawia, że nowe P (parametr) będzie miało postać następującej funkcji:

Symulacja szacowania rozkładu, z którego w statystycznym rozumieniu w konkretnej maszynie „było generowane” prawdopodobieństwo wygranej, przedstawiona jest na rysunku poniżej (Rysunek 2.). Zauważmy, że założeniem w tej sytuacji (rysunek 1 z 10) była całkowita niewiedza o naturze maszyny – każda wartość parametru jest w naszym przypadku równie prawdopodobna. Rozkład Beta przybiera postać rozkładu jednostajnego dla swoich parametrów równych 1.

Próbkowanie Thompsona
Powyżej ustaliliśmy, że umiemy modelować naszą niepewność w odniesieniu do parametru konkretnej maszyny. Ostatnim koniecznym krokiem w procedurze gry jest wybór, do której maszyny w danym momencie wrzucić monetę, gdy mamy ogląd parametrów modelu. Aby zminimalizować liczbę monet wrzucanych heurystycznie, korzystamy z metody zwanej próbkowaniem Thompsona. Każdy rozkład przypisany konkurującym o nasze pieniądze maszynom jest jednorazowo „próbkowany”, a moneta zostaje wrzucona do maszyny, z której próbka symulowanego rozkładu była większa niż pozostałe. Ta taktyka pozwala nam pokonać ograniczenie poprzedniej – nie stawiamy całej puli va banque na najbardziej obiecującego kandydata. Inwestujemy natomiast proporcjonalnie do szans, że dany parametr jest większy od pozostałych.

Powtarzając powyższe doświadczenie dla różnych ukrytych parametrów maszyn, otrzymujemy wartość oczekiwaną wygranych gier. Wykreślamy tę wartość na tle intuicyjnej taktyki (odniesienie do Rysunku 4.)
Podsumowanie
Na Rysunku 4. możemy zobaczyć, że na tym etapie estymowana wartość oczekiwana zwrotu z taktyki nr 2 jest większa od jej estymacji dla taktyki nr 1 i w tym momencie zatrzymujemy rozumowanie, pozostawiając pewne ważne kwestie statystyczne do wyszukania w literaturze.

W artykule przedstawiłem wstęp do zagadnienia nazywanego multi-armed bandid. Bayesowska teoria decyzji pozwala nam wyprowadzić dla tego problemu optymalną taktykę znajdywania kompromisu eksploracyjno-eksploatacyjnego. Algorytmami z tej rodziny estymujemy nie tylko cechy automatów (co jest dosyć niszowym zajęciem), ale przede wszystkim modelujemy cechy zarówno produktów (tj. reklamy, artykuły, wersje ofert lub wizualizacji strony), jak i samego użytkownika (np. demografia). Wiedza o tych cechach i odpowiednie dostosowywanie się jest kluczowe dla firm maksymalizujących swoje przychody w sieci.
Mateusz Łukasik – Data Scientist w Onwelo. Zawodowo tworzy systemy ekstrakcji i wnioskowania z danych. Prywatnie fan statystyki bayesowskiej oraz zarówno „dense”, jak i deep learningu.
Zostaw komentarz
Polecamy
Powroty do Onwelo – ostatnia część cyklu
Zjawisko Great Resignation zbiera żniwo w Stanach Zjednoczonych. Czy w Polsce mamy się czego bać? O tym, ale także o przyszłości polskiego rynku pracy i pracownikach pokolenia Z rozmawiamy z Anetą Baraś, naszą HR Director.
Jak komunikować się w międzynarodowym zespole?
Podczas pracy w międzynarodowych zespołach i projektach prędzej czy później zetkniemy się z różnicami kulturowymi, które mogą nam utrudniać komunikację i skuteczną współpracę. Jak sobie z tym poradzić?
Dobrze wracać tam, gdzie się było już
Z Rafałem Leśnickim rozmawiamy o tym, dlaczego warto utrzymywać dobre relacje z byłym pracodawcą i jak się nam to może zwrócić w przyszłości.
Powroty do Onwelo – ostatnia część cyklu
Zjawisko Great Resignation zbiera żniwo w Stanach Zjednoczonych. Czy w Polsce mamy się czego bać? O tym, ale także o przyszłości polskiego rynku pracy i pracownikach pokolenia Z rozmawiamy z Anetą Baraś, naszą HR Director.
Jak komunikować się w międzynarodowym zespole?
Podczas pracy w międzynarodowych zespołach i projektach prędzej czy później zetkniemy się z różnicami kulturowymi, które mogą nam utrudniać komunikację i skuteczną współpracę. Jak sobie z tym poradzić?