Overview

Appendix (meerarmige bandiet)

Rekenkundige en theoretische details

Ten eerste is het belangrijk in gedachten te houden dat de naam 'meerarmige bandiet' een probleem beschrijft waarvoor al meerdere 'oplossingen' zijn voorgesteld. Wanneer u een boek raadpleegt over 'Bekrachtiging leren' vindt u in het inleidende hoofdstuk verschillende benaderingen met betrekking tot meerarmige bandieten. De wiskunde achter het 'meerarmige bandiet'-probleem is zo ingewikkeld dat in de praktijk nagenoeg gelijke, heuristische oplossingen worden gebruikt. De wiskundige complexiteit is fijntjes samengevat in een beroemde uitspraak van Peter Whittle (Whittle, 1979):

[Het bandietprobleem] werd geformuleerd tijdens de [Tweede Wereld]oorlog en geallieerde analisten braken hun hoofd over de oplossing. Er werd daarom gesuggereerd om het probleem op Duitsland te gooien als het ultieme intellectuele sabotagemiddel.

Wij gebruiken een heuristiek bekend als de Thompson-steekproef of Randomized Probability Matching (gerandomiseerde waarschijnlijkheidsmatching) omdat het veel van de beste eigenschappen van deze heuristieken combineert. In [5] leest u meer over deze techniek, en in [2] , [3] en [4] leest u meer over de wiskundige eigenschappen ervan.

Waarschijnlijkheid optimale arm

De Thompson-steekproef schrijft sessies aan armen toe in verhouding tot de waarschijnlijkheid dat iedere arm optimaal is. Dit is een Bayesiaanse berekening. θ = (θ1, θ2,..., θk) duidt de de vector van conversieratio's voor armen aan 1, …, k, y duidt de tot nu toe geobserveerde data in het experiment aan. We modelleren y als een vector van onafhankelijke binomiale uitkomsten en nemen onafhankelijke, uniforme a-priori voor θ. Ia(θ) duidt de indicator van het evenement aan dat arm a optimaal is. We kunnen dan schrijven:

P(Ia) = ∫Ia(θ) p(θ|y) dθ

Deze integraal kan in gesloten vorm worden uitgevoerd (hoewel de gesloten vorm-oplossing gecompliceerde, speciale functies zoals incomplete bètafunctie inhoudt), of door numerieke integratie. In elk geval wordt de berekening snel instabiel, zelfs bij relatief kleine waarden van y. De waarschijnlijkheid dat één arm optimaal is, kan met simulatie op stabiele wijze worden berekend. Ieder element van θ is een onafhankelijke gerandomiseerde variabele van de bètaverdeling. Simuleer een grote matrix met trekkingen van θ uit de relevante bètaverdelingen, waar de rijen van de matrix willekeurige trekkingen voorstellen, en de kolommen het k aantal armen van het experiment representeren. Een Monte Carlo-schatting van de waarschijnlijkheid dat arm a optimaal is, is het empirische deel van de rijen waarvoor arm a de grootste gesimuleerde waarde had. De waarschijnlijkheid dat iedere arm het origineel verslaat kan op gelijke wijze worden berekend.

Overgebleven waarde

De simulatie die de waarschijnlijkheden voor de optimale arm produceert, kan ook de verdeling van de overgebleven waarde produceren in het experiment. De overgebleven waarde is de a-posteriori verdeling van (θmax-θ*)/θ*, waar θmax de grootste waarde is van θ, en θ* de grootste waarde is van θ voor de arm die de grootste kans heeft optimaal te zijn. Ter illustratie van de berekening: stel dat er drie armen met 20, 30 en 40 sessies zijn die 12, 20 en 30 conversies hebben gegenereerd. De waarschijnlijkheden voor de optimale arm zijn grofweg: 0,09, 0,20 en 0,71. De eerste zes trekkingen uit de Monte Carlo-simulatie van θ kunnen de overgebleven waarde hebben:

[.1] [.2] [.3]
[1,] 0,54 0,73 0,74
[2,] 0,55 0,66 0,73
[3,] 0,53 0,81 0,80
[4,] 0,57 0,50 0,65
[5,] 0,52 0,67 0,83
[6,] 0,65 0,84 0,63

We berekenen de waarde per rij door het grootste element uit die rij van het element in kolom 3 af te trekken (omdat arm 3 de grootste kans heeft om de optimale arm te zijn). In de eerste twee rijen is de waarde nul omdat de grootste trekking plaatsvindt in kolom 3. De waarde in de derde rij is 0,01/0,80 want kolom is 2 0,01 groter dan kolom 3. Als we iedere rij naar beneden blijven gaan, krijgen we een verdeling van waarden die we kunnen uitzetten in een histogram zoals het linker paneel van figuur A1. Arm 3 heeft een waarschijnlijkheid van 71 procent om de beste arm te zijn. De waarde van het overschakelen van arm 3 naar een andere arm is daarom nul in 71 procent van de gevallen. Het 95e percentiel van de waardeverdeling is de 'potentiële overgebleven waarde' in het experiment. In dit geval is dat ongeveer 0,16. U interpreteert dit cijfer als: 'We zijn nog steeds onzeker over de conversieratio van arm 3, maar ongeacht het percentage, kan één van de andere armen dit met maximaal 16 procent verslaan.'

In het rechter paneel in figuur A1 ziet u wat er gebeurt met de verdeling van overgebleven waarden naarmate het experiment vordert. Stel dat iedere arm vijfmaal de steekproefgrootte heeft (dus 100, 150 en 200 sessies), met vijfmaal het aantal conversies (60, 100, 150). Wanneer de omvang van de steekproef groter wordt, ontstaat er meer zekerheid over de conversieratio's van de armen. Arm 3 heeft nu een kans van 95 procent om de optimale arm te zijn. Het 95e percentiel van de verdeling van overgebleven waarden is dus nul.

Figuur A1. De verdeling van de overgebleven waarden in een experiment. De verticale lijn is in ieder geval het 95ste percentiel, of de potentiële overgebleven waarde.
Was dit nuttig?
Hoe kunnen we dit verbeteren?