Ramiona, pociągnięcia, nagrody
Rząd automatów do gry
Wyobraź sobie K automatów do gry ustawionych w rzędzie. Każdy automat wypłaca inną średnią nagrodę, ale nie znasz żadnej z tych średnich. Na każdym kroku wybierasz jeden automat, pociągasz za jego dźwignię i obserwujesz wypłatę. Twój cel: zmaksymalizować całkowitą nagrodę po wielu pociągnięciach.
To ustawienie definiuje problem wieloramiennego bandyty. K = liczba ramion. Pociągnięcie wybiera jedno ramię. Nagroda pochodzi z ukrytego rozkładu tego ramienia. mean_reward(k) ramienia k śledzi bieżącą średnią po pociągnięciach k.
Eksploracja vs Eksploatacja
Dwa naciski działają przeciwko sobie:
Eksploatacja pociąga za ramię z najwyższą obserwowaną średnią nagrodą. Zachłanna. Ryzyko: ramię, które wyglądało świetnie po 2 pociągnięciach, może wrócić do niższej prawdziwej średniej.
Eksploracja pociąga za mniej przetestowane ramię, aby zmniejszyć niepewność. Ryzyko: czas spędzony na eksploracji kosztuje nagrody, które mógłbyś zebrać z znanego dobrego ramienia.
Dobra polityka łączy oba. Czysta eksploatacja blokuje wczesnych zwycięzców na zawsze. Czysta eksploracja nigdy nie zbiera wypłaty.
Ramiona ANDREI = Źródła danych
ANDREA traktuje trening jako bandytę. Każde źródło danych (hermes3-general, gutenberg, dictionary, synthetic-chat, smoltalk itp.) działa jako ramię. Każdy krok treningowy pociąga jedno ramię: ładuje dokument z tego źródła, uruchamia forward pass, obserwuje redukcję straty. Średnia nagroda na źródło śledzi, o ile to źródło poprawia stratę średnio.
Dlaczego to pasuje: potrzeby modelu zmieniają się podczas treningu. Wczesne kroki korzystają z szerokiego kontaktu (wiele źródeł). Późniejsze kroki korzystają z celowanego polerowania (kilka źródeł o wysokiej nagrodzie). Bandyt adaptuje się; stały stosunek próbkowania nie może.
Nazewnictwo elementów
Wynik UCB1
Auer, Cesa-Bianchi & Fischer, 2002
Peter Auer i współpracownicy opublikowali UCB1 w 2002 roku jako politykę bandyta o skończonym czasie z granicą żalu O(log N). UCB1 wybiera ramię, łącząc jego bieżącą średnią nagrodę z bonusem eksploracji, który maleje w miarę pociągania ramienia.
Wzór
UCB(k) = mean_reward(k) + C * sqrt(ln(N) / n_k)
Element po elemencie:
- mean_reward(k): średnia nagroda obserwowana dla ramienia k w ciągu jego n_k pociągnięć. Termin eksploatacji.
- N: całkowita liczba pociągnięć wszystkich ramion do tej pory. Rośnie na każdym kroku.
- n_k: pociągnięcia ramienia k konkretnie. Rośnie tylko wtedy, gdy k zostanie wybrane.
- C: stała eksploracji. Standardowa wartość z podręczników: 1.4 (sqrt(2)). ANDREA używa C=0.5.
- sqrt(ln(N) / n_k): promień ufności. Rzadko pociągane ramię ma małe n_k i otrzymuje dużą premię; dobrze pociągane ramię ma duże n_k i otrzymuje małą premię.
Dlaczego wzór działa
ln(N) rośnie powoli (logarytmicznie), więc licznik wzrasta łagodnie wraz z całkowitym doświadczeniem. n_k w mianowniku zmniejsza ten termin, gdy dowody gromadzą się dla konkretnego ramienia. Pierwiastek kwadratowy złagadza reakcję, co zapobiega dominacji pojedynczego niedostatecznie zbadanego ramienia na zawsze.
Wybieranie przez argmax_k UCB(k) na każdym kroku automatycznie równoważy obie presje. Brak parametru epsilon, brak harmonogramu, brak temperatury. Matematyka to załatwia.
Oblicz wynik UCB
Dlaczego C=0.5 zamiast 1.4
Wartość z podręcznika
Auer, Cesa-Bianchi & Fischer wyprowadzają granicę żalu zakładając, że nagrody leżą w [0, 1]. Granica obowiązuje dla C = sqrt(2) approx 1.414. Większość podręczników naucza C=1.4 jako bezpiecznej wartości domyślnej.
Magnitudy nagród ANDREA
ANDREA raportuje ulepszenia straty na krok jako nagrodę. Surowe ulepszenia wynoszą około 0.001 (strata spada z 4.521 do 4.520). Po czynniku skalowania 1000x (omówionym w aktywności 78, atrybucja nagród), skalowane nagrody osiągają magnitudę blisko 1.0. Średnie nagrody w historii ramienia stabilizują się w paśmie 0.5 do 3.0.
Teraz rozważ bonus eksploracji przy C=1.4 z N=10000, n_k=100:
1.4 sqrt(ln(10000) / 100) = 1.4 sqrt(9.21 / 100) = 1.4 * 0.303 = 0.425
0.425 mieści się w paśmie nagród. Dopuszczalne. Teraz n_k=10 (rzadkie ramię):
1.4 sqrt(9.21 / 10) = 1.4 0.960 = 1.344
1.344 znajduje się POWYŻEJ większości obserwowanych średnich nagród. Eksploracja dominuje: rzadkie ramię wygrywa niezależnie od jego rzeczywistej średniej. Przy wielu źródłach i długich przebiegach treningowych, to zalewa harmonogram ramionami o niskiej średniej.
Poprawka: C=0.5
0.5 sqrt(9.21 / 10) = 0.5 0.960 = 0.480
0.480 znajduje się poniżej większości średnich nagród. Eksploracja nadal zachodzi (rzadkie ramiona nadal otrzymują bonus), ale mean_reward prowadzi. ANDREA bardziej eksploatuje, mniej eksploruje i unika dominacji eksploracji.
Strojenie jako inżynieria, nie teoria
Teoretyczne ograniczenie z podręcznika zakłada nagrody w [0, 1]. Nagrody ANDREA żyją w przybliżeniu w [0, 5]. Skalowanie stałej dopasowuje stałą do wielkości nagrody. Ten sam algorytm, skalibrowane środowisko.
Diagnozuj Dominację Eksploracji
Co Następne
Co Masz
UCB1 wybiera ramię z najwyższym górnym ograniczeniem ufności. Ograniczenie łączy mean_reward (eksploatacja) z sqrt(ln(N) / n_k) skalowanym przez C (eksploracja). ANDREA dostraja C=0.5, ponieważ nagrody krokowe mieszczą się w paśmie 0.5 do 3.0, a podręcznikowe 1.4 zalewa harmonogram ramionami o niskiej średniej.
Co Pozostało
Vanilla UCB1 wybiera jeden ramion naraz. ANDREA wybiera kilka ramion fokusowych na fazę, najpierw miesza losowe ramiona, & trzyma każdą fazę przez 7 do 42 kroków. Ta struktura (aktywność 77: fazy kostkowe) zapobiega UCB nadmiernemu zaangażowaniu w wczesnych zwycięzców, jednocześnie pozwalając mu skoncentrować wysiłek.
Atrybucja nagród (aktywność 78) pokazuje, skąd naprawdę pochodzi mean_reward(k). Podłogi & kary epokowe (aktywność 79) nakładają ochronne reguły na wyjście UCB.
Referencje
- Auer, Cesa-Bianchi, Fischer (2002). "Finite-time Analysis of the Multiarmed Bandit Problem." Machine Learning, 47, 235-256.
- Whitepaper ANDREA, sekcje 3.1 i 3.4.