Czym jest Próbkowanie Thompsona (Thompson sampling)?
Próbkowanie Thompsona, znane też jako Thompson sampling lub skrótowo TS, to bayesowska strategia sekwencyjnego podejmowania decyzji, która równoważy eksplorację oraz eksploatację w problemach typu wielozbrojny bandyta. Metoda pozwala systematycznie wybierać akcje – na przykład wyświetlane reklamy, warianty interfejsu czy hipotezy w eksperymentach A/B – na podstawie rozkładu posterior, czyli uaktualnianej wiedzy o prawdopodobieństwie sukcesu każdej opcji.
Kontekst historyczny
Technikę zaproponował William R. Thompson w 1933 roku na łamach Biometrika, opisując bayesowskie podejście do problemu wyboru między dwiema terapiami medycznymi. Choć idea czekała dziesięciolecia na szersze zastosowanie, renesans algorytmów typu bandyta oraz rozwój uczenia maszynowego po 2010 roku sprawiły, że Próbkowanie Thompsona stało się popularnym standardem w firmach technologicznych i instytucjach badawczych.
Jak dokładnie działa Próbkowanie Thompsona (Thompson sampling)
Algorytm utrzymuje rozkład prawdopodobieństwa skuteczności każdej akcji, najczęściej modelowany za pomocą parametrów beta w przypadku nagród zero–jedynkowych lub normalnych dla wartości ciągłych. Przy każdym kroku losuje próbkę z posterioru dla każdej opcji, a następnie wybiera tę o najwyższej wylosowanej wartości. Po zaobserwowaniu nagrody algorytm aktualizuje rozkłady, dzięki czemu bilety o słabych wynikach stopniowo tracą szansę na wybór, choć nigdy nie są całkowicie eliminowane. Ta stochastyczna procedura w naturalny sposób harmonizuje eksplorację z eksploatacją bez konieczności ustalania z góry arbitralnych współczynników, jak ma to miejsce w klasycznym podejściu ε-greedy.
Zastosowania w praktyce
Wielu operatorów platform reklamowych stosuje TS do optymalizacji doboru banerów, minimalizując koszty kampanii przy jednoczesnym wyszukiwaniu nowych ciekawych kreacji. W handlu elektronicznym metoda wspiera dynamiczne ustalanie cen i rekomendacje produktów, a w branży medycznej służy do adaptacyjnego przydzielania pacjentów do terapii w badaniach klinicznych. Jej wszechstronność sprawia, że pojawia się także w eksploracji hiperparametrów, sterowaniu robotami oraz grach online.
Zalety i ograniczenia
Kluczową zaletą jest eleganckie wykorzystanie informacji bayesowskiej, co prowadzi do niskiego żalu kumulacyjnego oraz mniejszej liczby ręcznie dostrajanych parametrów. Stochastyczny charakter wyboru zmniejsza ryzyko utykania w lokalnych optimum w porównaniu z metodami deterministycznymi. Ograniczeniem bywa jednak rosnąca złożoność obliczeniowa przy dużych przestrzeniach akcji lub skomplikowanych modelach rozkładów posterior, a także konieczność poprawnego zdefiniowania rozkładu prior, co nie zawsze jest trywialne.
Na co uważać?
W praktyce warto monitorować konwergencję posteriorów, ponieważ błędne założenia priory mogą prowadzić do przesadnej eksploatacji nieoptymalnych akcji. W systemach o dużej dynamice danych trzeba rozważyć zapominanie części obserwacji lub wprowadzenie wag czasowych, aby algorytm nie bazował na nieaktualnych informacjach. Ponadto implementacje oparte na przybliżeniach, takich jak próbki Monte Carlo czy variational inference, wymagają starannego testowania stabilności numerycznej.
Dodatkowe źródła
Szczegółowe omówienie oryginalnej koncepcji można znaleźć w artykule W.R. Thompsona z 1933 roku dostępnym w archiwum Biometrika. Zwięzły przegląd współczesnych zastosowań przedstawia publikacja na arXiv. Praktyczne wskazówki implementacyjne wraz z kodem przykładów oferuje również hasło Wikipedia.
