Armar, drag, belöningar
En rad med spelautomater
Föreställ dig K spelautomater i rad. Varje maskin ger en annan genomsnittlig belöning, men du känner inte till något av genomsnittsvärdena. Varje steg väljer du en maskin, drar i spaken, & observerar utbetalningen. Ditt mål: maximera total belöning över många drag.
Denna uppställning definierar ett multi-armed bandit-problem. K = antal armar. Ett drag väljer en arm. Belöningen kommer från den armens dolda fördelning. mean_reward(k) för arm k spårar det löpande genomsnittet över drag av k.
Utforskning vs Utnyttjande
Två krafter drar åt motsatta håll:
Utnyttjande drar i armen med det högsta observerade medelbelöningen. Girigt. Risk: en arm som såg bra ut efter 2 drag kan regressera till ett lägre sant medelvärde.
Utforskning drar i en mindre testad arm för att minska osäkerheten. Risk: tid spenderad på utforskning kostar belöning du kunde ha samlat från en känd bra arm.
En bra policy blandar båda. Ren exploatering låser in tidiga vinnare för alltid. Ren utforskning samlar aldrig in någon utdelning.
ANDREA:s Armar = Datakällor
ANDREA ramar in träning som en bandit. Varje datakälla (hermes3-general, gutenberg, dictionary, synthetic-chat, smoltalk, etc.) fungerar som en arm. Varje träningssteg drar i en arm: ladda ett dokument från den källan, kör en forward pass, observera förlustreduktion. Medelbelöning per källa spårar hur mycket den källan förbättrar förlusten i genomsnitt.
Varför detta passar: modellens behov förändras under träning. Tidiga steg gynnas av bred exponering (många källor). Sena steg gynnas av riktad polering (några hög-belöningskällor). En bandit anpassar sig; ett fast samplingförhållande kan inte det.
Benämna Delarna
UCB1-poängen
Auer, Cesa-Bianchi & Fischer, 2002
Peter Auer och kollegor publicerade UCB1 år 2002 som en finit-tids bandit-policy med en regret-gräns på O(log N). UCB1 väljer en arm genom att kombinera dess nuvarande genomsnittliga belöning med en explorationsbonus som minskar ju mer armen dras.
Formeln
UCB(k) = mean_reward(k) + C * sqrt(ln(N) / n_k)
Term för term:
- mean_reward(k): genomsnittlig belöning observerad för arm k över dess n_k drag. Exploateringsdelen.
- N: totala antal drag över alla armar hittills. Växer varje steg.
- n_k: drag av arm k specifikt. Växer bara när k väljs.
- C: explorationskonstant. Standardvärde i läroböcker: 1.4 (sqrt(2)). ANDREA använder C=0.5.
- sqrt(ln(N) / n_k): konfidensradie. En sällan dragen arm har liten n_k & får en stor bonus; en väl dragen arm har stor n_k & får en liten bonus.
Varför formeln fungerar
ln(N) växer långsamt (logaritmiskt), så täljaren stiger försiktigt med total erfarenhet. n_k i nämnaren minskar termen ju mer bevis som samlas för en specifik arm. Kvadratroten mildrar responsen, vilket hindrar en enda underutforskad arm från att dominera för evigt.
Välja med argmax_k UCB(k) varje steg balanserar båda trycken automatiskt. Ingen epsilon-parameter, ingen schema, ingen temperatur. Matematiken hanterar det.
Beräkna en UCB-poäng
Varför C=0.5 istället för 1.4
Lärobokens värde
Auer, Cesa-Bianchi & Fischer härleder en regret-gräns antagandes att belöningar ligger i [0, 1]. Gränsen gäller för C = sqrt(2) approx 1.414. De flesta läroböcker lär ut C=1.4 som ett säkert standardvärde.
ANDREA:s belöningsstorlekar
ANDREA rapporterar förbättringar i förlust per steg som belöning. Råa förbättringar ligger runt 0.001 (förlust sjunker från 4.521 till 4.520). Efter 1000x skalningsfaktorn (som täcks i aktivitet 78, reward attribution), hamnar skalade belöningar nära 1.0 i storlek. Medelbelöningar över en arms historia stabiliseras i ett band på 0.5 till 3.0.
Överväg nu explorationsbonusen vid C=1.4 med 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 ligger inne i belöningsbandet. Acceptabelt. Nu n_k=10 (en sällsynt arm):
1.4 sqrt(9.21 / 10) = 1.4 0.960 = 1.344
1.344 ligger ÖVER de flesta observerade medelbelöningar. Utforskning dominerar: den sällsynta armen vinner oavsett dess faktiska medelvärde. Med många källor & långa träningskörningar översvämmas schemat med låg-medelvärdesarmar.
Lösningen: C=0.5
0.5 sqrt(9.21 / 10) = 0.5 0.960 = 0.480
0.480 ligger under de flesta belöningsmedelvärden. Utforskning sker fortfarande (sällsynta armar får fortfarande en bonus), men mean_reward leder. ANDREA utnyttjar mer, utforskar mindre, & undviker utforskningsdominans.
Inställning som ingenjörskonst, inte teori
Lärobokens gräns antar belöningar i [0, 1]. ANDREA:s belöningar lever i ungefär [0, 5]. Skalning av konstanten matchar konstanten till belöningsmagnituden. Samma algoritm, kalibrerad miljö.
Diagnostisera Utforskningsdominans
Vad kommer härnäst
Vad du har
UCB1 väljer armen med högsta övre konfidensgräns. Gränsen kombinerar mean_reward (utnyttja) med sqrt(ln(N) / n_k) skalat med C (utforska). ANDREA justerar C=0.5 eftersom stegvisa belöningar ligger i ett band 0.5 till 3.0, & lärobokens 1.4 översvämmar schemat med låg-medelvärdesarmar.
Vad som återstår
Vanilla UCB1 väljer en arm åt gången. ANDREA väljer flera fokusarmar per fas, blandar slumpmässiga armar först, & håller varje fas i 7 till 42 steg. Den strukturen (aktivitet 77: tärningsfaser) hindrar UCB från att överåta sig till tidiga vinnare samtidigt som den fortfarande låter det koncentrera ansträngningen.
Belöningsattribution (aktivitet 78) visar var mean_reward(k) faktiskt kommer ifrån. Golven & epokstraff (aktivitet 79) lägger skyddande regler ovanpå UCB-utdata.
Referens
- Auer, Cesa-Bianchi, Fischer (2002). "Finite-time Analysis of the Multiarmed Bandit Problem." Machine Learning, 47, 235-256.
- ANDREA whitepaper, avsnitt 3.1 & 3.4.