Flerarmad bandit

Vad är problemet med flerarmad bandit?

I marknadsföringstermer är en lösning med flerarmad bandit 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 fördelas till varianter som presterar sämre.

Begreppet "flerarmad bandit" kommer från ett hypotetiskt experiment där en person måste välja mellan flera åtgärder (t.ex. spelautomater, "enarmade banditer"), var och en med en okänd utbetalning. Målet är att genom en serie val komma fram till det bästa eller mest lönsamma utfallet. I början av experimentet, när oddsen och utbetalningarna är okända, måste spelaren bestämma vilken maskin som ska dras, i vilken ordning och hur många gånger. Detta är "problemet med flerarmad bandit".

Exempel på flerarmad bandit

Ett verkligt exempel på en flerarmad bandit är när en webbplats för nyheter måste fatta beslut om vilka artiklar som ska visas för en besökare. Eftersom det inte finns någon information om besökaren är alla klickresultat okända. Den första frågan är vilka artiklar som kommer att få flest klick? Och i vilken ordning ska de visas? Webbplatsens mål är att maximera engagemanget, men de har många olika typer av innehåll att välja mellan och de saknar data som kan hjälpa dem att följa en specifik strategi.

Nyhetswebbplatsen har ett liknande problem när den ska 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äckligt med information om besökaren för att kunna följa en specifik annonseringsstrategi. På samma sätt som med nyhetsartiklar har de vanligtvis ett stort antal annonser att välja mellan. Vilka annonser kommer att ge maximala intäkter för deras nyhetswebbplats?

Webbplatsen måste fatta en rad beslut, vart och ett med okänt resultat och "utbetalning".

Lösningar med flerarmad bandit

Det finns många olika lösningar som datavetare har utvecklat för att ta itu med problemet med flerarmad bandit. Nedan följer en lista över några av de mest använda lösningarna för flerarmade banditer:

1. Epsilon-greedy

   Detta är en algoritm för att kontinuerligt balansera utforskning och exploatering. (I "giriga" experiment dras alltid spaken med den högsta kända utbetalningen, utom när en slumpmässig åtgärd vidtas). En slumpmässigt vald arm dras en bråkdel ε av tiden. Resterande 1ε av tiden dras armen med den högsta kända utbetalningen.

2. Övre konfidensgräns

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

3. Thompson-sampling (Bayesiansk)

   Med denna slumpmässiga sannolikhetsmatchningsstrategi bör antalet dragningar för en viss spak matcha dess faktiska sannolikhet att vara den optimala spaken.

Vad är en kontextuell bandit?

I ett verkligt scenario har vi ibland data som kan hjälpa till att informera beslutsfattandet när vi väljer mellan de olika åtgärderna i en situation med flerarmad bandit. Denna information är den "kontextuella banditen", det sammanhang och den miljö där experimentet äger rum.

Vid webbplatsoptimering förlitar sig kontextuella banditer på inkommande data om användarkontext eftersom de kan användas för att fatta bättre algoritmiska beslut i realtid.

Du kan till exempel använda en kontextuell bandit för att välja ett innehåll eller en annons som ska visas på din webbplats för att optimera klickfrekvensen. Kontexten är all historisk eller aktuell information som du har om användaren, t.ex. tidigare besökta sidor, information om tidigare köp, enhetsinformation eller geolokalisering.

Om du är en nyhetsportal och du vet att en person som kommer till din webbplats har läst underhållningsartiklar tidigare, kan du välja din bästa underhållningsartikel som ska visas högst upp på sidan så att de kan se den. Om du kan se att din användare befinner sig i Miami kan du visa det lokala vädret eller annan relevant information.

Flerarmade banditer och A/B-testning

När du bestämmer dig för om du ska använda flerarmade banditer istället för A/B-testning måste du väga exploatering mot utforskning (ibland känt som "tjäna eller lära".)

Med A/B-testning har du en begränsad period av ren utforskning där du fördelar trafik i lika stora mängder till version A och version B. När du har utsett en vinnare går du in i en lång period av exploatering där 100% av användarna går 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 flerarmad bandit-testning är testerna adaptiva och inkluderar perioder av utforskning och exploatering samtidigt. De flyttar trafiken gradvis mot vinnande variationer, istället för att tvinga dig att vänta med att utropa en vinnare i slutet av ett experiment. Den här processen är snabbare och effektivare eftersom mindre tid går åt till att skicka trafik till uppenbart sämre varianter.

En av de största nackdelarna med flerarmad bandit-testning är dess beräkningskomplexitet. Det är helt enkelt svårare och mer resurskrävande att köra flerarmade bandit-tester.

Det finns några kända situationer där flerarmad bandit-testning vanligtvis fungerar bäst:

1. Rubriker och kortsiktiga kampanjer

   Alternativkostnaden för att vänta på resultaten av A/B-testningar gör bandit-algoritmer till ett bättre val för kortlivade innehållsdelar som test av rubriker för nya artiklar eller semesterkampanjer.

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 en A/B-testning över tid, ger flerarmade banditer ett alternativ till upprepade omtestningar genom att kontinuerligt utforska.

3. Målgruppsinriktning

   Målgruppsinriktning är ett annat exempel på en långsiktig användning av banditalgoritmer. Om vissa typer av användare är vanligare än andra kan den flerarmade banditen tillämpa inlärda regler för målgruppsinriktning tidigare för vanligare användare, samtidigt som man fortsätter att experimentera med mindre vanliga användare.

4. Automatisering för skala upp

   Om du har flera komponenter som kontinuerligt ska optimeras ger metoden med flerarmad bandit dig ett ramverk för att delvis automatisera optimeringsprocessen för lågriskproblem, som kan vara för kostsamma att analysera individuellt.

Hur Optimizely använder flerarmade banditer

Optimizely Web Experimentation och Feature Experimentation använder några algoritmer för flerarmad bandit för att på ett intelligent sätt ändra trafikfördelningen mellan olika variationer för att uppnå ett mål. Beroende på ditt mål väljer du mellan målen:

• Hitta statistiskt signifikanta variationer så snart som möjligt - Stats Accelerator

  • Minskar experimentets varaktighet genom att visa fler besökare den variation som har en bättre chans att nå statistisk signifikans.
  • Maximerar antalet lärdomar från experiment inom en tidsram, så att du spenderar mindre tid på att vänta på resultat.
  • Försök att upptäcka så många signifikanta variationer som möjligt.

• Maximera belöning och minimera ånger - Flerarmad bandit (MAB)

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