W uczeniu się przez wzmacnianie agent lub decydent generuje dane szkoleniowe wchodząc w interakcję ze światem. Agent musi poznać konsekwencje swoich działań metodą prób i błędów, a nie bezpośrednio mu mówić, jakie działanie należy podjąć.

Problem wielorękiego bandyty

W Uczeniu się przez wzmacnianie używamy problemu wielorękiego bandyty, aby sformalizować pojęcie podejmowania decyzji w warunkach niepewności przy użyciu uzbrojonych bandytów. Osoba podejmująca decyzję lub agent jest obecna w zadaniu Wielorękiego Bandyty, aby wybierać pomiędzy k-różnymi działaniami i otrzymuje nagrodę w zależności od wybranej akcji. Problem bandyty służy do opisu podstawowych pojęć związanych z uczeniem się przez wzmacnianie, takich jak nagrody, etapy czasowe i wartości.

Powyższy obrazek przedstawia automat znany również jako bandyta z dwiema dźwigniami. Zakładamy, że każda dźwignia ma odrębną dystrybucję nagród i istnieje co najmniej jedna dźwignia, która generuje maksymalną nagrodę.

Rozkład prawdopodobieństwa nagrody odpowiadającej każdej dźwigni jest inny i nieznany graczowi (decydentowi). Dlatego celem jest określenie, którą dźwignię należy pociągnąć, aby uzyskać maksymalną nagrodę po danym zestawie prób.

Na przykład:

Wyobraź sobie próbę reklamy online, w której reklamodawca chce zmierzyć współczynnik klikalności trzech różnych reklam tego samego produktu. Za każdym razem, gdy użytkownik odwiedza witrynę, reklamodawca wyświetla losowo reklamę. Reklamodawca monitoruje następnie, czy użytkownik kliknie reklamę, czy nie. Po pewnym czasie reklamodawca zauważa, że ​​jedna reklama wydaje się działać lepiej niż pozostałe. Reklamodawca musi teraz zdecydować, czy pozostać przy najskuteczniejszej reklamie, czy kontynuować badanie z randomizacją.
Jeśli reklamodawca wyświetla tylko jedną reklamę, nie może już zbierać danych o pozostałych dwóch reklamach. Być może któraś z reklam jest lepsza, tylko przez przypadek wydaje się gorsza. Jeśli pozostałe dwie reklamy są gorsze, kontynuacja badania może niekorzystnie wpłynąć na współczynnik klikalności. Ta próba reklamy jest przykładem podejmowania decyzji w warunkach niepewności.
W powyższym przykładzie rolę agenta pełni reklamodawca. Reklamodawca ma do wyboru trzy różne działania, aby wyświetlić pierwszą, drugą lub trzecią reklamę. Każda reklama to akcja. Wybranie tej reklamy zapewnia nieznaną nagrodę. Wreszcie zysk reklamodawcy po reklamie jest nagrodą, którą reklamodawca otrzymuje.

Wartości akcji:

Aby reklamodawca mógł zdecydować, które działanie jest najlepsze, musimy zdefiniować wartość podjęcia każdego działania. Wartości te definiujemy za pomocą funkcji wartość-działanie, posługując się językiem prawdopodobieństwa. Wartość wyboru akcji Q_*(A) definiuje się jako oczekiwaną nagrodę R_T otrzymujemy podejmując działanie A z możliwego zestawu działań.

Celem agenta jest maksymalizacja oczekiwanej nagrody poprzez wybranie akcji o najwyższej wartości akcji.

Oszacowanie wartości działania:

układ siatki

Ponieważ wartość wyboru akcji, tj. Q_*(A) nie jest znany agentowi, dlatego użyjemy metody średnia próbki sposób go oszacować.

Eksploracja a eksploatacja:

Chciwe działanie: gdy agent wybiera akcję, która ma obecnie największą szacunkową wartość. Agent wykorzystuje swoją obecną wiedzę, wybierając zachłanne działanie. Działanie inne niż chciwe: gdy agent nie wybierze największej szacunkowej wartości i nie poświęci natychmiastowej nagrody, mając nadzieję na uzyskanie większej ilości informacji o innych działaniach. Eksploracja: pozwala agentowi poszerzyć swoją wiedzę na temat każdego działania. Miejmy nadzieję, że przyniesie to długoterminowe korzyści. Wyzysk: pozwala agentowi wybrać zachłanne działanie, aby uzyskać jak największą nagrodę w zamian za krótkoterminowe korzyści. Czysty, zachłanny wybór działań może prowadzić do nieoptymalnego zachowania.

Pojawia się dylemat między eksploracją a eksploatacją, ponieważ agent nie może wybrać jednocześnie eksploracji i eksploatacji. Dlatego używamy Górna granica ufności Algorytm rozwiązywania dylematu eksploracja-eksploatacja

Wybór akcji z górnym poziomem ufności:
Wybór działań o wyższym poziomie ufności wykorzystuje niepewność w szacunkach wartości działania w celu zrównoważenia poszukiwań i wydobycia. Ponieważ dokładność szacunków wartości działania w przypadku korzystania z wyselekcjonowanego zestawu nagród jest nieodłącznie związana z niepewnością, firma UCB wykorzystuje niepewność szacunków do napędzania eksploracji.

Q_T(A) tutaj przedstawia bieżący szacunek działań A o czasie T . Wybieramy akcję, która ma najwyższą szacowaną wartość akcji plus termin eksploracji ograniczony górną pewnością.

Pytanie na powyższym obrazku przedstawia aktualną szacunkową wartość działania A . Nawiasy przedstawiają przedział ufności w przybliżeniu Q_*(A) co mówi, że jesteśmy pewni rzeczywistej wartości działania A leży gdzieś w tym regionie.

najlepszy uśmiech na świecie

Dolny nawias nazywa się dolną granicą, a górny nawias jest górną granicą. Obszar w nawiasach to przedział ufności reprezentujący niepewność szacunków. Jeśli region jest bardzo mały, wtedy mamy pewność, że rzeczywista wartość działania A jest blisko naszej szacunkowej wartości. Z drugiej strony, jeśli region jest duży, wówczas stajemy się niepewni co do wartości działania A jest blisko naszej szacunkowej wartości.

The Górna granica ufności kieruje się zasadą optymizmu w obliczu niepewności, która oznacza, że ​​jeśli nie jesteśmy pewni jakiegoś działania, powinniśmy z optymizmem założyć, że jest to działanie właściwe.

Załóżmy na przykład, że na poniższym obrazku mamy te cztery działania z powiązanymi niepewnościami, a nasz agent nie ma pojęcia, które działanie jest najlepsze. Zatem zgodnie z algorytmem UCB optymistycznie wybierze akcję, która ma najwyższą górną granicę, tj. A . Robiąc to, albo będzie to miało najwyższą wartość i otrzyma najwyższą nagrodę, albo biorąc to, dowiemy się o działaniu, o którym najmniej wiemy.

Załóżmy, że po wybraniu akcji A kończymy w stanie przedstawionym na obrazku poniżej. Tym razem UCB wybierze akcję B od P(B) ma najwyższą górną granicę ufności, ponieważ jego oszacowanie wartości działania jest najwyższe, mimo że przedział ufności jest mały.

Początkowo UCB eksploruje więcej, aby systematycznie zmniejszać niepewność, ale z biegiem czasu zakres eksploracji ogranicza się. Możemy zatem powiedzieć, że UCB uzyskuje średnio większą nagrodę niż inne algorytmy, takie jak zachłanny Epsilon, optymistyczne wartości początkowe itp.