Overview

Meerarmige-bandietexperimenten

Door Steven L. Scott, PhD, Sr. Economic Analyst

In dit artikel wordt de statistische engine beschreven die achter Contentexperimenten van Analytics zit. Analytics gebruikt de aanpak van de meerarmige bandiet om online experimenten te beheren. Een meerarmige-bandietexperiment is een type experiment waarbij:

  • het doel is de beste of meest rendabele actie te vinden
  • de gerandomiseerde verdeling kan worden bijgewerkt tijdens het verloop van het experiment

Met de term 'meerarmige bandiet' wordt een gedachtenexperiment aangeduid waarin een gokker verschillende gokautomaten ('eenarmige bandieten') bespeelt met potentieel verschillende verwachte uitbetalingen. Het doel is om de gokkast te vinden met de beste uitbetalingsverhouding, maar ook om de winst de maximaliseren. Het fundamentele dilemma is dat enerzijds armen met een bewezen hoog rendement moeten worden 'uitgebuit' maar anderzijds nieuwe of ogenschijnlijk minderwaardige armen moeten worden 'verkend' voor het geval deze nog lucratiever zijn. Er zijn zeer geavanceerde wiskundige modellen voor het beheren van het bandietprobleem die wij gebruiken in Contentexperimenten van Analytics.

Aan het begin van het document vindt u enkele achtergrondinformatie over het gebruik van meerarmige bandieten in Analytics. Vervolgens worden twee voorbeelden gepresenteerd van gesimuleerde experimenten met ons algoritme voor de meerarmige bandiet. Daarna worden enkele veelgestelde vragen behandeld en aan het eind vindt u een appendix met rekenkundige en theoretische technische details.

Achtergrond

De werking van de bandieten

Tweemaal per dag bekijken we opnieuw uw experiment om te zien hoe elk van de varianten heeft gepresteerd en passen het gedeelte van het verkeer aan dat elke variant vanaf dat moment ontvangt. Een variant die goed presteert, krijgt meer verkeer en een variant die duidelijk slechter presteert, krijgt minder verkeer. De aanpassingen die we doen, zijn gebaseerd op een statistische formule (zie de appendix voor details) die kijkt naar de combinatie van steekproefomvang en prestatiestatistieken, zodat we er zeker van kunnen zijn dat we aanpassingen doen op basis van daadwerkelijke prestatieverschillen in plaats van toeval. Naarmate het experiment vordert, krijgen we meer inzicht in de relatieve opbrengst, waardoor we betere varianten kunnen kiezen.

Voordelen

Experimenten op basis van meerarmige bandieten zijn doorgaans efficiënter dan 'klassieke' A-B-experimenten op basis van toetsing met statistische hypotheses. Ze zijn statistisch gezien even geldig en kunnen onder vele omstandigheden veel sneller antwoorden genereren. Ze zijn efficiënter omdat ze verkeer geleidelijk naar winnende varianten verplaatsen, in plaats van dat u moet wachten op de uiteindelijke uitslag van het experiment. Ze kunnen sneller zijn omdat steekproeven die aan duidelijk slechtere varianten zouden zijn toegewezen, nu naar potentiële winnaars gaan. Met de extra gegevens die worden verzameld over de goed presterende varianten kunnen de goede varianten sneller van de slechte worden gescheiden.

Kort gezegd: bandieten maken experimenten efficiënter, zodat u er meer tegelijk kunt uitvoeren. Bovendien kunt u een groter gedeelte van uw verkeer toewijzen aan uw experimenten omdat verkeer automatisch naar beter presterende pagina's wordt gestuurd.

Voorbeelden

Een eenvoudige A/B-test

Stel dat u site een conversieratio van 4 procent heeft. U experimenteert met de nieuwe versie van de site die in 5 procent van de gevallen conversies genereert. U weet natuurlijk niet de exacte conversieratio's, daarom experimenteert u. Laten we echter aannemen dat u wilt dat uw experimenten een conversieratio van 5 procent kan herkennen met een statistische waarschijnlijkheid van 95 procent. Door een standaard onderscheidend vermogen1 weet u dat u 22.330 observaties nodig heeft (11.165 per arm) voor een 95 procent kans om een verandering in conversieratio van 0,04 in 0,05 te detecteren. Als uw experiment dus 100 sessies per dag krijgt, zal het 223 dagen duren. In een standaardexperiment wacht u 223 dagen, voert u een hypothese-test uit en krijgt u vervolgens uw antwoord.

Nu kunnen we de 100 sessies per dag met de meerarmige bandiet gaan beheren. Op de eerste dag worden ongeveer 50 sessies toegewezen aan elke arm en kijken we naar de resultaten. We gebruiken het theorema van Bayes om de waarschijnlijkheid te berekenen dat de variant beter is dan het origineel2. Eén min dit getal is de waarschijnlijkheid dat het origineel beter is. Stel nu dat het origineel de eerste dag mazzel heeft gehad, en een 70 procent kans toonde om beter te zijn. Dan wijzen we op de tweede dag 70 procent van het verkeer toe aan het origineel en 30 procent aan de variant. Aan het einde van de tweede dag verzamelen we al het verkeer dat tot dan toe is waargenomen (van beide dagen), en berekenen we voor elk van de armen opnieuw de waarschijnlijkheid dat deze de beste is. Dit resulteert in de weergavewegingen voor dag drie. Dit proces wordt herhaald totdat aan een reeks stopregels is voldaan. Meer informatie over stopregels vindt u hieronder.

In figuur 1 ziet u een simulatie van wat kan gebeuren met deze instellingen. U ziet de weergavewegingen voor het origineel (de zwarte lijn) en de variant (de rode stippellijn) die in feite heen en weer gaan totdat de variant uiteindelijk de grens van 95 procent betrouwbaarheid overschrijdt. (De twee percentages moeten samen 100 procent zijn, dus als de ene omhoog gaat, gaat de ander omlaag). Dit experiment werd afgerond in 66 dagen, en het heeft u dus 157 testdagen bespaard.

Figuur 1. Een simulatie van de waarschijnlijkheid dat één van de armen optimaal is voor een simpel twee-armig experiment. Deze wegingen drukken de fractie van het verkeer uit dat dagelijks aan elke arm wordt toegewezen.

Dit is uiteraard slechts een voorbeeld. We hebben de simulatie 500 keer opnieuw uitgevoerd om te zien hoe goed de bandieten het doen in herhaalde steekproeven. De verdeling van resultaten kunt u zien in figuur 2. Gemiddeld eindigt de test 175 dagen eerder dan de klassieke test op basis van onderscheidend vermogen. Dit bespaart gemiddeld 97,5 conversies.

Figuur 2. De verdelingen van de hoeveelheid bespaarde tijd en het aantal bespaarde conversies ten opzichte van een klassiek experiment gepland met een onderscheidend vermogen. Uitgegaan van een conversieratio van 4 procent voor het origineel en 5 procent voor de variant.

Maar wat is de statistische validiteit? Wordt door het gebruik van minder gegevens niet ook de foutratio vergroot? Niet echt. In de 500 bovenstaande experimenten vond de bandiet in 482 gevallen de correcte arm. Dat is een validiteit van 96,4%, met ongeveer dezelfde foutratio als de klassieke test. Er waren een aantal experimenten waarbij de bandiet er daadwerkelijk langer over deed dan de analyse met onderscheidend vermogen, maar die maken samen slechts 1 procent van alle tests uit (5 op de 500).

We hebben ook het tegenovergestelde experiment uitgevoerd, waarbij het origineel een succespercentage van 5 procent had en de variant één van 4 procent. De resultaten waren in wezen symmetrisch. Ook in dit geval vond de bandiet de correcte arm in 482 van de 500 pogingen. Het bespaarde gemiddeld 171,8 dagen ten opzichte van het klassiek experiment en het gemiddelde aantal bespaarde conversies was 98,7.

Het experiment stopzetten

We laten de bandieten standaard twee weken experimenteren. Daarna houden we twee statistieken bij.

Ten eerste de waarschijnlijkheid dat de variant beter is dan het origineel. Als we 95 procent zeker zijn dat een variant beter is dan het origineel roept Analytics een winnaar uit. De gebruiker kan zowel de de minimum duur van twee weken als het betrouwbaarheidsniveau van 95 procent aanpassen.

De tweede statistiek die we bijhouden is de 'resterende potentiële waarde van het experiment', die zeer bruikbaar is bij een experiment van meerdere armen. Op ieder moment is er een 'kampioensarm' waarvan wordt verondersteld dat die de beste is. Als het experiment 'nu' eindigt, zou worden gekozen voor de kampioen. De 'resterende waarde' in een experiment is de hoeveelheid verhoging in conversieratio die u kunt krijgen door om te schakelen van de kampioen. De zoektocht naar deze waarde is de essentie van het experiment. Als u 100 procent zeker weet dat de kampioen de beste arm is, heeft het experiment geen waarde meer en dus ook geen nut meer. Maar als u slechts 70 procent zeker weet dat een arm optimaal is, is er 30 procent kans dat de andere arm toch beter is en kunnen we met de regel van Bayes een verdeling opstellen van hoeveel beter deze is. (Zie de appendix voor rekenkundige details).

Analytics beëindigt het experiment op het moment dat er ten minste een 95 procent waarschijnlijkheid is dat resterende waarde van het experiment lager is dan 1 procent van de conversieratio van de kampioen. Dit betreft een verbetering van 1 procent en niet een verbetering van een percentagepunt. Dus als de beste arm een conversieratio van 4 procent heeft, beëindigen we het experiment zodra de resterende waarde van het experiment lager is dan 0,04 percentagepunten van de conversieratio.

Het beëindigen van een experiment op basis van resterende potentiële waarde is een goede keuze omdat het goed omgaat met gelijkspel. In een experiment met twee armen kan het gebeuren dat twee of meer armen ongeveer gelijk presteren en dat het dus niet uitmaakt welke arm wordt gekozen. In dit geval wilt u het experiment niet laten duren tot u de de optimale arm heeft gevonden (omdat er twee optimale armen zijn). U wilt het experiment laten duren totdat u zeker weet dat het wisselen van varianten niet echt helpt.

Complexere experimenten

De meerarmige bandiet ten opzichte van klassieke experimenten biedt een groter voordeel bij complexere expe. U heeft waarschijnlijk meerdere ideeën ter verbetering van uw website, dus wilt u meer dan één variant per keer testen. Stel dat u vijf varianten plus het origineel wilt tes. U gaat een berekening maken waarbij u het origineel vergelijkt met de meest verschillende variant, dus we moeten enkele aanpassingen doen om rekening te houden met meerdere vergelijkingen. De Bonferroni-correctie is een gemakkelijke (maar ook enigszins ouderwetse) aanpassing die kan worden geïmplementeerd door het significantieniveau van de hypothesetest te delen door het aantal armen. Vervolgens maken we de standaardberekening met een significantieniveau van 0,05 / (6 - 1), waaruit blijkt dat we 15.307 observaties nodig hebben per arm van het experiment. Met zes armen is dat ongeveer 91.842 observaties. Uitgaande van 100 sessies per dag betekent dit dat het experiment theoretisch 919 dagen zou duren (meer dan tweeënhalf jaar). Praktisch gezien heeft het geen zin om een experiment dat zo lang duurt uit te voeren, maar we kunnen natuurlijk bij wijze van gedachtenexperiment een simulatie ervan uitvoeren.

Vervolgens voeren we een simulatie uit van hetzelfde experiment als het meerarmige-bandietexperiment. Wederom wordt uitgegaan van een conversieratio van 4 procent en een optimale arm met een conversieratio van 5 procent. De andere vier armen bevatten één suboptimale arm die het origineel verslaat met een conversieratio van 4,5 procent en drie mindere varianten met percentages van 3, 2 en 3,5 procent. In figuur 3 ziet u de verdeling van de resultaten. De gemiddelde duur van het experiment is 88 dagen (ten opzichte van 919 dagen voor het klassieke experiment) en het gemiddelde aantal bespaarde conversies is 1173. Er zit een lange uitloop aan de verdeling van experimentduur (deze experimenten zijn niet altijd snel afgelopen), maar zelfs in het ergste geval werden alsnog 800 conversies bespaard ten opzichte van het klassieke experiment.

Figuur 3. Besparing ten opzichte van een zes-armig experiment, in verhouding tot een klassiek experiment met onderscheidend vermogen dat gebruik maakt van de Bonferroni-correctie. Het linker paneel toont het vereiste aantal dagen voor beëindiging van het experiment, waarbij de verticale lijn de vereiste tijd voor het uitvoeren van een klassiek experiment met onderscheidend vermogen weergeeft. Het rechter paneel toont het aantal conversies die dankzij de bandiet zijn bespaard.

De kostenbesparingen zijn deels toe te schrijven aan de korte duur van het experiment, en deels toe te schrijven aan het feit dat het experiment minder verspilt. In figuur 4 ziet u het verloop van alle weergavewegingen voor alle armen in de eerste 500 simulaties. In het begin ontstaat er enige verwarring omdat moet worden uitgezocht welke armen goed presteren en welke niet, maar al snel wordt aan de zeer slecht presterende armen een lage weging toegekend. In dit geval heeft de originele arm beginnersgeluk, waardoor deze het langer uithoudt dan enkele andere armen die me. Maar na 50 dagen stabiliseert het experiment in een twee-armige strijd tussen het origineel en de uiteindelijke winnaar. Wanneer de andere armen zijn uitgeschakeld, worden de 100 observaties per dag verdeeld over het origineel en de uiteindelijke winnaar. De bandiet verdeelt de observaties op efficiënte wijze vanuit economisch perspectief (over de armen die naar verwachting het meeste rendement opleveren) en vanuit statistisch perspectief (naar de armen waar wij het meeste over willen leren).

Figuur 4. Geschiedenis van de weergegeven wegingen van één van de zesarmige experimenten.

Figuur 5 toont de dagelijkse kosten van de meerarmige bandiet ten opzichte van een 'helderziende'-strategie waarbij altijd arm 2, de optimale arm, wordt gebruikt. (Dit is natuurlijk niet eerlijk omdat we in de praktijk niet weten welke arm optimaal is, maar het is een nuttige uitgangswaarde). Gemiddeld kost iedere observatie die is toegewezen aan het origineel ons 0,01 van een conversie omdat de conversieratio van het origineel 0,01 minder dan arm 2 is. Eveneens kost iedere observatie die bijvoorbeeld is toegewezen aan arm 5 ons 0,03 conversies omdat de conversieratio 0,03 minder is dan arm 2. Wanneer we het aantal observaties dat is toegewezen aan elke arm vermenigvuldigen met de kosten van de arm, en daarna de som berekenen van alle armen, krijgen we de kosten voor het uitvoeren van het experiment op die dag. In het klassieke experiment worden aan elke arm 100/6 sessies per dag toegewezen (gemiddeld, afhankelijk van de wijze waarop gedeeltelijke observaties zijn toegewezen). In totaal kost het klassieke experiment ons 1333 conversies per dag dat het wordt uitgevoerd. De rode lijn in figuur 5 toont de kosten om de bandiet iedere dag uit te voeren. Na verloop van tijd wordt het experiment zuiniger naarmate er een lage weging wordt gegeven aan mindere armen.

Figuur 5. Kosten per dag voor het bandietexperiment. De constante kosten per dag van het klassieke experiment worden getoond door de horizontale stippellijn.

1De R-functie power.prop.test heeft elk onderscheidend vermogen in dit artikel berekend.

2Zie appendix voor de details van de berekening. U kunt deze ook overslaan.

Was dit nuttig?
Hoe kunnen we dit verbeteren?