Wprowadzenie do wielorękich bandytów

Copyright 2021 Autorzy TF-Agents.

Wstęp

Multi-Armed Bandit (MAB) to platforma uczenia maszynowego, w której agent musi wybierać działania (ramiona), aby zmaksymalizować skumulowaną nagrodę w dłuższej perspektywie. W każdej rundzie agent otrzymuje informacje o aktualnym stanie (kontekście), następnie na podstawie tych informacji i doświadczenia zebranego w poprzednich rundach wybiera akcję. Na koniec każdej rundy agent otrzymuje nagrodę powiązaną z wybraną akcją.

Być może najczystszym przykładem jest problem, który pożyczył jej nazwę do MAB: wyobraź sobie, że mamy do czynienia z k automatów (jednorękich bandytów) i musimy dowiedzieć się, który z nich ma najlepszą wygraną, nie tracąc zbyt dużo pieniędzy.

Jednokrotne wypróbowanie każdej maszyny, a następnie wybranie tej, która zapłaciła najwięcej, nie byłoby dobrą strategią: agent mógłby wybrać maszynę, która na początku miała szczęśliwy wynik, ale ogólnie jest nieoptymalna. Zamiast tego agent powinien wielokrotnie wracać do wybierania maszyn, które nie wyglądają tak dobrze, aby zebrać o nich więcej informacji. To jest główne wyzwanie w wielorękich bandytach: agent musi znaleźć odpowiednią mieszankę między wykorzystaniem wcześniejszej wiedzy a eksploracją, aby uniknąć przeoczenia optymalnych działań.

Bardziej praktyczne przykłady MAB obejmują informację poboczną za każdym razem, gdy uczeń podejmuje decyzję. Tę informację poboczną nazywamy „kontekstem” lub „obserwacją”.

Wieloręcy bandyci i nauka wsparcia

Dlaczego w bibliotece TF-Agents jest pakiet MAB? Jaki jest związek między RL i MAB? Wieloręki bandyta może być traktowany jako szczególny przypadek uczenia się przez wsparcie. Zacytować Intro do RL :

Na każdym kroku czasowym, agent wykonuje działania na środowisko na podstawie jego polityki $\pi(a_t|s_t)$, gdzie $s_t$ jest bieżąca obserwacja ze środowiska, a otrzymuje nagrodę $r_{t+1}$ i obok obserwacji $s_{t+1}$ ze środowiska . Celem jest udoskonalenie polityki tak, aby zmaksymalizować sumę nagród (zwrotu).

W ogólnym przypadku RL, kolejna obserwacja $s_{t+1}$ zależy od stanu poprzedniego $s_t$ a akcja $a_t$ podjętej przez politykę. Ta ostatnia część oddziela MAB od RL: w MAB kolejny stan, czyli obserwacja, nie zależy od działania wybranego przez agenta.

To podobieństwo pozwala nam ponownie wykorzystać wszystkie koncepcje, które istnieją w TF-Agents.

• Środowisko wyprowadza obserwacje, i reaguje na działania z nagrodami.
• Polityka wyprowadza akcję na podstawie obserwacji i
• Środek wielokrotnie aktualizuje politykę opartą na poprzednich krotki obserwacja-action-nagroda.

Grzybowe środowisko

W celach ilustracyjnych używamy przykładu zabawki o nazwie „Środowisko grzybowe”. Grzyb zestaw danych ( Schlimmer, 1981 ) składa się z oznakowanych przykładów jadalnych i trujących grzybów. Funkcje obejmują kształty, kolory, rozmiary różnych części grzyba, a także zapach i wiele innych.

Zbiór danych grzybowych, podobnie jak wszystkie zbiory danych nadzorowanego uczenia się, można przekształcić w kontekstowy problem MAB. Używamy metody wykorzystywane przez Riquelme et al. (2018) . W tej konwersji agent otrzymuje cechy grzyba, decyduje się go zjeść lub nie. Zjedzenie jadalnego grzyba daje nagrodę +5, podczas gdy zjedzenie trującego grzyba daje +5 lub -35 z równym prawdopodobieństwem. Nie zjedzenie grzyba daje 0 nagrody, niezależnie od rodzaju grzyba. Poniższa tabela zawiera podsumowanie przydziałów nagród:

           | edible | poisonous
-----------|--------|----------
eating it  |     +5 | -35 / +5
leaving it |      0 |        0

Agent LinUCB

Dobre wyniki w kontekstowym środowisku bandytów wymagają dobrego oszacowania funkcji nagrody za każde działanie, biorąc pod uwagę obserwację. Jedną z możliwości jest oszacowanie funkcji nagrody za pomocą funkcji liniowych. Oznacza to, że dla każdego działania $i$, staramy się znaleźć parametru $\theta_i\in\mathbb R^d$ dla których szacunki

$r_{t, i} \sim \langle v_t, \theta_i\rangle$

są jak najbardziej zbliżone do rzeczywistości. Tutaj $v_t\in\mathbb R^d$ jest kontekst odbierane w etapie czas $t$. Następnie, jeżeli środek jest bardzo pewny w swoich szacunkach, można go wybrać $\arg\max_{1, ..., K}\langle v_t, \theta_k\rangle$ aby uzyskać najwyższą oczekiwaną nagrodę.

Jak wyjaśniono powyżej, samo wybranie ramienia z najlepiej oszacowaną nagrodą nie prowadzi do dobrej strategii. Istnieje wiele różnych sposobów, aby mieszać eksploatacji i eksploracji w liniowych estymatora czynników, a jednym z najbardziej znanych jest górna granica ufności liniowy algorytm (LinUCB) (patrz np Li i wsp. 2010 ). LinUCB składa się z dwóch głównych elementów konstrukcyjnych (z pominięciem niektórych szczegółów):

1. Utrzymuje szacunki parametrów każdego ramienia z metodą najmniejszych kwadratów: $\hat\theta_i\sim X^+_i r_i$, gdzie $X_i$ i $r_i$ są ułożone w stos kontekstów i korzyści pocisków, gdy ramię $i$ zostało wybrane, $()^+$ jest odwrotnością pseudo .
2. Utrzymuje elipsoidy ufności zdefiniowane przez odwrotną kowariancji $X_i^\top X_i$ dla powyższych szacunków.

Główną ideą LinUCB jest „Optymizm w obliczu niepewności”. Agent uwzględnia poszukiwania poprzez podwyższenie szacunków o kwotę odpowiadającą wariancji tych szacunków. Czyli gdzie elipsoidy ufności przyjść na zdjęciu: na każdym ramieniu, optymistyczne oszacowanie jest $\hat r_i = \max_{\theta\in E_i}\langle v_t, \theta\rangle$, gdzie $E_i$ jest elipsoida wokół $\hat\theta_i$. W Wybiera agenta najlepiej patrząc ramię $\arg\max_i\hat r_i$.

Oczywiście powyższy opis jest tylko intuicyjnym, ale powierzchownym podsumowaniem tego, czym zajmuje się LinUCB. Implementacja można znaleźć w naszym kodzie tutaj

Co dalej?

Jeśli chcesz mieć bardziej szczegółowy poradnik na naszej biblioteki Bandits przyjrzeć naszym poradniku bandytów . Jeśli natomiast chciałbyś rozpocząć odkrywanie naszą bibliotekę od razu, można go znaleźć tutaj . Jeśli są jeszcze chętni, aby rozpocząć trening, spojrzeć na niektóre z naszych end-to-end przykładów tutaj , w tym powyżej opisanego środowiska grzybowa z LinUCB tutaj .