Multi-armed bandit

Vad är multi-armed bandit-problemet?

Inom marknadsföring är en multi-armed bandit-lösning en "smartare" eller mer komplex version av A/B-testning som använder maskininlärningsalgoritmer för att dynamiskt fördela trafik till varianter som presterar bra, samtidigt som mindre trafik allokeras till varianter som underpresterar.

Termen "multi-armed bandit" kommer från ett hypotetiskt experiment där en person måste välja mellan flera åtgärder (dvs. spelautomater, de så kallade "enarmade banditerna"). Målet är att fastställa det bästa eller mest lönsamma utfallet genom en serie val. I början av experimentet, när odds och utbetalningar är okända, måste spelaren avgöra vilken maskin som ska spelas, i vilken ordning och hur många gånger. Detta är "multi-armed bandit-problemet".

Exempel på multi-armed bandit

Ett verkligt exempel på ett multi-armed bandit-problem är när en nyhetswebbplats måste fatta beslut om vilka artiklar som ska visas för en besökare. Utan information om besökaren är alla klickutfall okända. Den första frågan är: vilka artiklar får flest klick? Och i vilken ordning ska de visas? Webbplatsens mål är att maximera engagemanget, men de har många innehållsalternativ att välja mellan och saknar data som skulle hjälpa dem att följa en specifik strategi.

Nyhetswebbplatsen har ett liknande problem när det gäller att välja vilka annonser som ska visas för besökarna. I det här fallet vill de maximera annonsintäkterna, men de kanske saknar tillräcklig information om besökaren för att följa en specifik annonsstrategi. I likhet med problemet med nyhetsartiklar har de vanligtvis ett stort antal annonser att välja mellan. Vilka annonser ger maximal intäkt för deras nyhetssajt?

Webbplatsen behöver fatta en serie beslut, vart och ett med okänt utfall och okänd "utbetalning".

Multi-armed bandit-lösningar

Det finns många olika lösningar som datavetare har utvecklat för att hantera multi-armed bandit-problemet. Nedan finns en lista över några av de vanligaste multi-armed bandit-lösningarna:

1. Epsilon-greedy

   Detta är en algoritm för att kontinuerligt balansera utforskning med utnyttjande. (I "greedy"-experiment dras alltid spaken med högst känd utbetalning, förutom när en slumpmässig åtgärd vidtas). En slumpmässigt vald arm dras en andel ε av tiden. Resterande 1-ε av tiden dras armen med högst känd utbetalning.

2. Upper confidence bound

   Denna strategi baseras på principen Optimism in the Face of Uncertainty och antar att de okända genomsnittliga utbetalningarna för varje arm kommer att vara så höga som möjligt, baserat på observerbar data.

3. Thompson Sampling (Bayesiansk)

   Med denna randomiserade sannolikhetsmatchningsstrategi ska antalet dragningar för en given spak motsvara dess faktiska sannolikhet att vara den optimala spaken.

Hur kontextuella banditer skiljer sig från vanliga multi-armed banditer

En kontextuell bandit är en avancerad personaliseringsalgoritm som förbättrar multi-armed bandit-metoden genom att inkludera användarspecifik data. Medan traditionella multi-armed banditer hjälper till att identifiera vinnande varianter, avgör kontextuella banditer vilken variant som fungerar bäst för varje unik besökare.

"Kontexten" avser besökarspecifik information som enhetstyp, plats, tidigare beteende eller köphistorik. Denna data gör det möjligt för maskininlärningsmodellen att fatta smartare beslut om vilket innehåll som ska visas för att maximera konverteringar.

Så fungerar kontextuella banditer:

1. Inlärningsperiod: Modellen börjar med 100 % utforskning och tilldelar slumpmässigt varianter till besökare för att samla in mångsidig data för förutsägelser.
2. Balansering av utforskning och utnyttjande: När tillräckligt med besökarbeteendedata har samlats in börjar modellen utnyttja (servera personaliserade varianter). Den justerar dynamiskt utforsknings-/utnyttjandegraden allt eftersom fler händelser tas emot.
3. Kontinuerlig anpassning: Modellen behåller viss utforskning (maximalt 95 % utnyttjande) för att säkerställa kontinuerligt lärande och undvika missade möjligheter

Istället för att manuellt skapa komplexa riktningsregler för olika användarsegment lär sig kontextuella banditer automatiskt dessa samband och serverar den mest relevanta upplevelsen till varje besökare i realtid. Detta tillvägagångssätt eliminerar gissningar och levererar verklig 1:1-personalisering i stor skala – avgörande i dagens konkurrensutsatta miljö där uppmärksamheten är begränsad och förväntningarna på personalisering är höga.

Den viktigaste skillnaden mellan kontextuella banditer och traditionella multi-armed banditer är kontext. Medan vanliga multi-armed banditer söker en enda vinnande variant för alla användare, identifierar kontextuella banditer den bästa varianten för varje användare baserat på deras specifika attribut.

• A/B-testning: Fasta trafikfördelningar med en universallösning vid vinnarvalet
• Multi-armed banditer: Dynamisk trafikfördelning som söker en övergripande "bästa" variant
• Kontextuella banditer: Personaliserade upplevelser baserade på användarkontext (enhet, plats, beteende)

Multi-armed banditer vs. A/B-testning

När du ska avgöra om du ska använda multi-armed banditer istället för A/B-testning måste du väga avvägningen mellan utnyttjande och utforskning (ibland kallat "tjäna eller lära").

Nyckeln till att förstå skillnaden mellan traditionell A/B-testning och multi-armed banditer är konceptet utnyttjande kontra utforskning:

• Utforskning: Visa olika varianter för besökare för att lära sig vilken som presterar bäst
• Utnyttjande: Visa den bäst presterande varianten för att maximera konverteringar

Med A/B-testning har du en begränsad period av ren utforskning där du fördelar trafik i lika delar till Version A och Version B. När du utser en vinnare övergår du till en lång period av utnyttjande, där 100 % av användarna dirigeras till den vinnande varianten. Ett problem med detta tillvägagångssätt är att du slösar resurser på den förlorande varianten medan du försöker samla in data och lära dig vilken som är vinnaren.

Med multi-armed bandit-testning är testerna adaptiva och inkluderar perioder av utforskning och utnyttjande samtidigt. De flyttar trafik gradvis mot vinnande varianter, istället för att tvinga dig att vänta med att utse en vinnare i slutet av ett experiment. Denna process är snabbare och mer effektiv eftersom mindre tid läggs på att skicka trafik till uppenbart sämre varianter.

En av de främsta nackdelarna med multi-armed bandit-testning är dess beräkningsmässiga komplexitet. Enkelt uttryckt är det svårare och mer resurskrävande att köra multi-armed bandit-tester.

När ska man använda multi-armed banditer

Det finns kända situationer där multi-armed bandit-testning vanligtvis fungerar bäst:

1. Rubriker och kortsiktiga kampanjer: Alternativkostnaden för att vänta på resultaten av A/B-tester gör banditalgoritmer till ett bättre val för kortlivat innehåll som rubriktest för nya artiklar eller helgkampanjer.

2. Långsiktiga dynamiska förändringar: När det som testas förändras tillräckligt mycket för att ogiltigförklara resultaten av ett A/B-test över tid, erbjuder multi-armed banditer ett alternativ till upprepad omtestning genom att kontinuerligt utforska.

3. Målgruppsinriktning: Målgruppsinriktning är ytterligare ett exempel på långsiktig användning av banditalgoritmer. Om vissa typer av användare är vanligare än andra kan multi-armed bandit-algoritmen tillämpa inlärda riktningsregler snabbare för vanligare användare, samtidigt som den fortsätter att experimentera med mindre vanliga användare.

4. Automatisering för skalbarhet: Om du har flera komponenter att kontinuerligt optimera ger multi-armed bandit-metoden dig ett ramverk för att delvis automatisera optimeringsprocessen för problem med låg risk, som kan vara för kostsamma att analysera individuellt.

När ska man använda kontextuella banditer

Kontextuella banditer levererar betydande affärsvärde i dessa scenarier:

1. Personalisering i stor skala: När du behöver erbjuda verkligt personaliserade upplevelser för varje användare istället för universallösningar, och leverera rätt innehåll till rätt person vid rätt tidpunkt.
2. Dynamisk anpassning: När du behöver ett system som serverar den bästa varianten i varje session, även när användarpreferenser förändras.
3. Eliminering av alternativkostnader: Till skillnad från A/B-tester som kräver veckor eller månader för att uppnå statistisk signifikans, börjar kontextuella banditer optimera omedelbart och minskar exponeringen mot underpresterande varianter i realtid.
4. Optimering med lågt underhåll: För sidor där innehållet inte ändras alltför ofta. Allt eftersom tiden går blir ML-modellen skarpare med den data den samlar in, vilket gör detta till en "ställ in och glöm"-optimering som kan köras kontinuerligt.

Hur Optimizely använder multi-armed banditer

Optimizely Web Experimentation och Feature Experimentation använder ett antal multi-armed bandit-algoritmer för att intelligent ändra trafikfördelningen mellan varianter för att uppnå ett mål. Beroende på ditt mål väljer du mellan följande målsättningar:

1. Stats accelerator

Hitta en statistiskt signifikant variant så snabbt som möjligt.

• Minskar experimentets varaktighet genom att visa fler besökare den variant som har bättre chans att nå statistisk signifikans.
• Maximerar antalet insikter från experiment under en tidsperiod, så att du lägger mindre tid på att vänta på resultat.
• Försöker upptäcka så många signifikanta varianter som möjligt.

2. Multi-armed bandit (MAB)

Maximera belöning och minimera förlust.

• Låter dig utnyttja så mycket värde som möjligt från den ledande varianten under experimentets livscykel, så att du undviker kostnaden för att visa suboptimala upplevelser.
• Genererar inte statistisk signifikans.
• Använder Thompson Sampling-algoritmen för binära mätvärden.
• Använder Epsilon-greedy-algoritmen för numeriska mätvärden.

3. Kontextuell bandit

Leverera verkligt personaliserade upplevelser.

• Avancerade trädbaserade maskininlärningsmodeller som matchar upplevelser till individuella användarkontexter
• Erbjuder 1:1-personalisering i stor skala utan manuell segmentering
• Bäst för att skapa varaktiga personaliseringsprogram som anpassar sig till förändrade användarbeteenden