Najlepszy algorytm bandyty?

Najbardziej znanym algorytmem bandyty jest górna granica ufności (UCB), która spopularyzowała tę klasę algorytmów. Od tego czasu zakładam, że są teraz lepsze algorytmy. Jaki jest obecnie najlepszy algorytm (pod względem wydajności empirycznej lub granic teoretycznych)? Czy ten algorytm jest w pewnym sensie optymalny?

Artykuł z NIPS 2011 („Analiza empiryczna próbkowania Thompsona”) pokazuje w eksperymentach, że próbkowanie Thompsona przewyższa UCB. UCB polega na wybraniu dźwigni, która obiecuje najwyższą nagrodę przy optymistycznych założeniach (tj. Wariancja oszacowania oczekiwanej nagrody jest wysoka, dlatego pociągasz za dźwignie, których nie znasz tak dobrze). Zamiast tego, próbkowanie Thompsona jest w pełni bayesowskie: generuje konfigurację bandytów (tj. Wektor oczekiwanych nagród) z dystrybucji tylnej, a następnie działa tak, jakby to była prawdziwa konfiguracja (tj. Pociąga dźwignię z najwyższą oczekiwaną nagrodą).

Zasada kontroli bayesowskiej („ Zasada minimalnej entropii względnej dla uczenia się i działania ”, JAIR), uogólnienie próbkowania Thompsona, wywodzi się z prób teoretycznych i przyczynowych informacji. W szczególności wykazano, że reguła kontroli bayesowskiej jest strategią optymalną, gdy chcesz zminimalizować KL między strategią a (nieznaną) strategią optymalną i jeśli bierzesz pod uwagę ograniczenia przyczynowe. Powodem, dla którego jest to ważne, jest to, że można to postrzegać jako rozszerzenie wnioskowania bayesowskiego na działania: wnioskowanie bayesowskie może być optymalną strategią przewidywania, gdy kryterium wydajności jest KL między estymatorem a (nieznanym) rozkładem prawdziwym.

UCB jest rzeczywiście prawie optymalny w przypadku stochastycznym (do współczynnika logarytmu T dla gry w rundzie T) i do luki w nierówności Pinskera w sensie bardziej zależnym od problemu. Niedawny artykuł Audiberta i Bubecka usuwa tę zależność od logów w najgorszym przypadku, ale ma gorszą sytuację w korzystnym przypadku, gdy różne ramiona mają dobrze rozdzielone nagrody.

Ogólnie rzecz biorąc, UCB jest jednym kandydatem z większej rodziny algorytmów. W dowolnym momencie gry możesz spojrzeć na wszystkie ramiona, które nie są „zdyskwalifikowane”, to znaczy, których górna granica pewności nie jest mniejsza niż dolna granica pewności jakiegoś ramienia. Wybór oparty na dowolnej dystrybucji takiej wykwalifikowanej broni stanowi ważną strategię i budzi podobny żal do stałych.

Z empirycznego punktu widzenia nie sądzę, że dokonano znaczącej oceny wielu różnych strategii, ale myślę, że UCB jest często całkiem niezły.

Większość najnowszych badań koncentruje się na rozszerzeniu problemów bandytów poza proste ustawienie z uzbrojeniem K ze stochastycznymi nagrodami, na bardzo duże (lub nieskończone) przestrzenie akcji, z lub bez informacji bocznych i pod stochastyczną lub przeciwną reakcją. Pracowano również w scenariuszach, w których kryteria wydajności są różne (takie jak tylko identyfikacja najlepszego ramienia).

Obecny stan techniki można podsumować następująco:

• stochastyczny: UCB i warianty (żałuje w )$R_T = O(\frac{K \log T}{\Delta})$
• przeciwny: EXP3 i warianty (żałuję w )$\tilde{R}_T = O(\sqrt{T K \log K})$
• kontekstowe: to skomplikowane

z oznacza liczbę rund, liczbę ramion, prawdziwa różnica między najlepszym i drugim najlepszym ramieniem (przerwa).$T$$K$$\Delta$