09 · Wzmocnienie · 4 min czytania · Interaktywne · aktualizacja
Na czym polega problem wielorękiego bandyty i jak go rozwiązać?
W skrócie
Wieloręki bandyta to dylemat: grać na opcji, która dotąd działała najlepiej, czy sprawdzać inne? Strategie ε-zachłanna, UCB i Thompsona godzą oba cele.
Co to jest
Problem wielorękiego bandyty (multi-armed bandit) to najprostsza postać dylematu eksploracji i eksploatacji. Stoisz przed kilkoma automatami do gry („jednorękimi bandytami”), każdy wypłaca wygraną z innym, nieznanym prawdopodobieństwem. Masz ograniczoną liczbę pociągnięć. W każdym ruchu wybierasz: grać na automacie, który dotąd wypadał najlepiej (eksploatacja), czy sprawdzić inny, o którym wiesz mało (eksploracja)?
To nie jest problem kasynowy, tylko model wielu realnych decyzji: którą wersję strony pokazać użytkownikowi, którą reklamę wyświetlić, który lek podać kolejnemu pacjentowi w badaniu adaptacyjnym, który nagłówek artykułu wybrać. W przeciwieństwie do klasycznego testu A/B bandyta uczy się w trakcie i stopniowo kieruje ruch do lepszej opcji, zamiast czekać do końca eksperymentu.
Mechanizm — dlaczego tak działa
Miarą jakości strategii jest żal (regret): o ile mniejsza jest suma wygranych od tej, którą dałoby granie od początku na najlepszym automacie. Granie losowe ma żal rosnący liniowo — tracisz stałą porcję w każdym ruchu. Celem jest żal rosnący wolniej niż liniowo, czyli coraz rzadsze błędy. Lai i Robbins (1985) pokazali, że w najlepszym razie żal rośnie logarytmicznie z liczbą ruchów.
Strategia zachłanna zawsze wybiera automat o najwyższej dotychczasowej średniej. Brzmi rozsądnie, ale ma zasadniczą wadę: jeśli najlepszy automat miał pecha w pierwszych próbach, jego średnia jest zaniżona i strategia nigdy więcej go nie wybierze. Nie ma więc szansy poprawić tej błędnej oceny. Zaniżone oceny utrwalają się, zawyżone same się korygują.
ε-zachłanna w ułamku ε ruchów (np. 10%) wybiera automat losowo. To gwarantuje, że każda ocena będzie z czasem korygowana, ale eksploruje na ślepo — tyle samo prób dostaje automat beznadziejny co obiecujący.
UCB (Upper Confidence Bound) wybiera automat o największej sumie: średnia + premia za niepewność, np. √(2·ln t / n), gdzie n to liczba prób danego automatu. Zasada „optymizmu w obliczu niepewności”: rzadko sprawdzany automat dostaje kredyt zaufania, a premia maleje, gdy zbieramy dane. UCB1 ma gwarancję logarytmicznego żalu, ale jego premia jest ostrożna i na krótkim horyzoncie potrafi eksplorować za dużo.
Próbkowanie Thompsona prowadzi dla każdego automatu rozkład a posteriori prawdopodobieństwa wygranej (dla wygranych 0/1 — rozkład beta). W każdym ruchu losuje jedną wartość z każdego rozkładu i gra na automacie z najwyższą wylosowaną. Automat wybierany jest z takim prawdopodobieństwem, z jakim jest najlepszy w świetle danych. Eksploracja sama wygasa, gdy rozkłady się zwężają.
Na przykładzie
Symulacja: pięć automatów z prawdopodobieństwem wygranej 0,20; 0,40; 0,50; 0,55 i 0,60, horyzont 1000 pociągnięć, 1000 powtórzeń z ustalonymi ziarnami losowymi. Maksymalnie można oczekiwać 600 wygranych. Granie losowe daje średni żal 149,9. Strategia zachłanna (po jednej próbie każdego automatu na start): 72,1 — a w 59% przebiegów w ostatnich 100 ruchach gra na najlepszym automacie rzadziej niż w połowie przypadków, bo utknęła na gorszym.
ε-zachłanna z ε = 0,1: żal 39,8; z ε = 0,05: 38,8. UCB1: 66,8 — na tak krótkim horyzoncie i przy bliskich sobie automatach (0,55 i 0,60) jego ostrożna premia każe eksplorować zbyt długo. Próbkowanie Thompsona: 33,1, czyli średnio 566,9 wygranych z możliwych 600; w ostatnich 100 ruchach gra na najlepszym automacie w 77,6% przypadków, a utknięcie zdarza się tylko w 11,6% przebiegów.
W praktyce
- Prostą symulację napiszesz w NumPy; próbkowanie Thompsona dla wygranych 0/1 to jedna linijka:
np.argmax(rng.beta(wins + 1, losses + 1)). - Na start wybierz próbkowanie Thompsona — jest proste, odporne i zwykle najlepsze w praktyce; ε-zachłanna to dobra, łatwa do wytłumaczenia alternatywa.
- Gdy nagrody zmieniają się w czasie, zapominaj stare dane (okno przesuwne, współczynnik dyskontowania), inaczej bandyta przegapi zmianę.
- Gdy decyzja zależy od cech użytkownika, potrzebny jest bandyta kontekstowy (np. LinUCB), a nie zwykły.
- Bandyta minimalizuje straty w trakcie, ale daje słabsze, obciążone oszacowania różnic między opcjami; gdy celem jest rzetelny pomiar efektu, lepszy jest klasyczny test A/B.
- Typowy błąd: strategia zachłanna „bo wystarczy wybrać najlepsze” — przegrywa właśnie przez brak eksploracji.
Najczęstsze pytania
- Czym różni się wieloręki bandyta od testu A/B?
- Test A/B dzieli ruch po równo do końca eksperymentu, a potem wybiera zwycięzcę — dobrze mierzy różnicę, ale przez cały test traci na gorszej wersji. Bandyta przesuwa ruch do lepszej opcji w trakcie, więc traci mniej, za to gorzej szacuje wielkość różnicy.
- Która strategia bandyty jest najlepsza?
- Nie ma jednej najlepszej we wszystkich warunkach. W wielu badaniach i zastosowaniach próbkowanie Thompsona wypada najlepiej lub prawie najlepiej. UCB ma mocne gwarancje teoretyczne. ε-zachłanna jest najprostsza i często wystarczająca.
- Jaki jest związek bandytów z uczeniem ze wzmocnieniem?
- Bandyta to uczenie ze wzmocnieniem bez stanów: decyzja nie zmienia sytuacji, w której podejmujesz następną. W pełnym uczeniu ze wzmocnieniem, np. Q-learningu, akcje przenoszą agenta do nowych stanów, a nagroda może przyjść dopiero po wielu krokach. Dylemat eksploracji i eksploatacji pozostaje ten sam.
Źródła
- Sutton R. S., Barto A. G., „Reinforcement Learning: An Introduction”, 2nd ed., MIT Press 2018, rozdz. 2 (Multi-armed Bandits).
- Lattimore T., Szepesvári C., „Bandit Algorithms”, Cambridge University Press 2020.
- Auer P., Cesa-Bianchi N., Fischer P., „Finite-time Analysis of the Multiarmed Bandit Problem”, Machine Learning 47, 2002.
- Thompson W. R., „On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples”, Biometrika 25(3–4), 1933.
- Lai T. L., Robbins H., „Asymptotically Efficient Adaptive Allocation Rules”, Advances in Applied Mathematics 6(1), 1985.