Armen, Trekkingen, Beloningen
Een Rij Gokkasten
Stel je K gokkasten in een rij voor. Elke kast betaalt een andere gemiddelde beloning, maar je kent geen van de gemiddelden. Elke stap kies je één kast, trek je aan de hendel, & observeer je een uitbetaling. Je doel: totale beloning maximaliseren over vele trekkingen.
Die opzet definieert een multi-armed bandit probleem. K = aantal armen. Een trekking kiest één arm. De beloning komt uit de verborgen verdeling van die arm. De mean_reward(k) van arm k volgt het lopende gemiddelde over trekkingen van k.
Exploratie vs Exploitatie
Twee krachten trekken tegen elkaar:
Exploitatie trekt de arm met de hoogste waargenomen gemiddelde beloning. Gulzig. Risico: een arm die er geweldig uitzag na 2 trekkingen kan terugvallen naar een lagere werkelijke gemiddelde waarde.
Exploratie trekt een minder geteste arm om onzekerheid te verminderen. Risico: tijd besteed aan exploratie kost beloning die je had kunnen verzamelen van een bekende goede arm.
Een goede policy combineert beide. Pure exploitatie sluit vroege winnaars voor altijd op. Pure exploratie verzamelt nooit een beloning.
ANDREA's Armen = Gegevensbronnen
ANDREA framed training als een bandit. Elke gegevensbron (hermes3-general, gutenberg, dictionary, synthetic-chat, smoltalk, etc.) fungeert als een arm. Elke trainingstap trekt aan één arm: laad een document van die bron, voer een forward pass uit, observeer verliesreductie. Gemiddelde beloning per bron volgt hoeveel die bron het verlies gemiddeld verbetert.
Waarom dit past: het model verandert tijdens training. Vroege stappen profiteren van brede blootstelling (veel bronnen). Latere stappen profiteren van gerichte polijsting (een paar bronnen met hoge beloning). Een bandit past zich aan; een vaste bemonsterratio kan dat niet.
De Onderdelen Benoemen
De UCB1 Score
Auer, Cesa-Bianchi & Fischer, 2002
Peter Auer & collega's publiceerden UCB1 in 2002 als een finite-time bandit-beleid met een regret bound van O(log N). UCB1 kiest een arm door het huidige gemiddelde reward te combineren met een exploration bonus die krimpt naarmate de arm meer wordt getrokken.
De Formule
UCB(k) = mean_reward(k) + C * sqrt(ln(N) / n_k)
Term voor term:
- mean_reward(k): gemiddelde beloning waargenomen voor arm k over zijn n_k pulls. Exploitatieterm.
- N: totale pulls over alle armen tot nu toe. Groeit elke stap.
- n_k: pulls van arm k specifiek. Groeit alleen wanneer k wordt gekozen.
- C: exploratieconstante. Standaard textbook-waarde: 1.4 (sqrt(2)). ANDREA gebruikt C=0.5.
- sqrt(ln(N) / n_k): betrouwbaarheidsstraal. Een zelden-getrokken arm heeft kleine n_k & krijgt een grote bonus; een goed-getrokken arm heeft grote n_k & krijgt een kleine bonus.
Waarom de formule werkt
ln(N) groeit langzaam (logaritmisch), dus de teller stijgt geleidelijk met totale ervaring. n_k in de noemer verkleint de term naarmate bewijs zich ophoopt voor een specifieke arm. Vierkantswortel verzacht de respons, waardoor een enkele onder-exploratie arm niet voor altijd domineert.
Kiezen door argmax_k UCB(k) elke stap balanceert beide drukken automatisch. Geen epsilon-parameter, geen schema, geen temperatuur. De wiskunde regelt het.
Bereken een UCB-score
Waarom C=0.5 in plaats van 1.4
De waarde uit het leerboek
Auer, Cesa-Bianchi & Fischer leiden een spijtgrens af onder de aanname dat beloningen in [0, 1] liggen. De grens geldt voor C = sqrt(2) approx 1.414. De meeste leerboeken leren C=1.4 als een veilige standaardinstelling.
Beloningsgrootte van ANDREA
ANDREA rapporteert per-stap verliesverbeteringen als beloning. Ruwe verbeteringen liggen rond 0.001 (verlies daalt van 4.521 naar 4.520). Na de schaalfactor van 1000x (behandeld in activiteit 78, beloningsattributie), landen de geschaalde beloningen rond 1.0 in grootte. Gemiddelde beloningen over de geschiedenis van een arm stabiliseren in een band van 0.5 tot 3.0.
Overweeg nu de exploratiebonus bij C=1.4 met 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 bevindt zich binnen de reward band. Tolerabel. Nu n_k=10 (een zeldzame arm):
1.4 sqrt(9.21 / 10) = 1.4 0.960 = 1.344
1.344 bevindt zich BOVEN de meeste waargenomen mean_rewards. Exploratie domineert: de zeldzame arm wint ongeacht zijn werkelijke gemiddelde. Met veel bronnen & lange training runs, vult dit de schedule met armen met lage gemiddelden.
De Oplossing: C=0.5
0.5 sqrt(9.21 / 10) = 0.5 0.960 = 0.480
0.480 ligt onder de meeste reward-gemiddelden. Exploratie gebeurt nog steeds (zeldzame armen krijgen nog een bonus), maar mean_reward leidt. ANDREA exploiteert meer, exploreert minder, & vermijdt exploratie-dominantie.
Tuning als Engineering, Niet Theorie
De textbook-grens gaat uit van rewards in [0, 1]. ANDREA's rewards liggen ruwweg in [0, 5]. De constante schalen past de constante aan de reward-magnitude aan. Zelfde algoritme, gekalibreerde omgeving.
Diagnose Exploratie Dominantie
Wat Hierna Komt
Wat Je Hebt
UCB1 kiest de arm met de hoogste upper confidence bound. De bound combineert mean_reward (exploiteer) met sqrt(ln(N) / n_k) geschaald door C (explore). ANDREA stemt C=0.5 af omdat de per-stap rewards in een band van 0.5 tot 3.0 liggen, & de textbook 1.4 de planning overspoelt met armen met lage gemiddelden.
Wat Rest Er Over
Vanilla UCB1 kiest één arm tegelijk. ANDREA kiest meerdere focusarmen per fase, mixt eerst willekeurige armen, & houdt elke fase 7 tot 42 stappen aan. Die structuur (activiteit 77: dobbelfasen) voorkomt dat UCB zich te veel vastbijt in vroege winnaars terwijl het toch inspanning kan concentreren.
Beloningsattributie (activiteit 78) toont waar mean_reward(k) echt vandaan komt. Bodems & epochstraffen (activiteit 79) leggen beschermende regels bovenop de UCB-uitvoer.
Referentie
- Auer, Cesa-Bianchi, Fischer (2002). "Finite-time Analysis of the Multiarmed Bandit Problem." Machine Learning, 47, 235-256.
- ANDREA whitepaper, secties 3.1 & 3.4.