Flerarmet banditt

Hva er det flerarmede bandittproblemet?

I markedsføringstermer er en løsning med flerarmede banditter en "smartere" eller mer kompleks versjon av A/B-testing som bruker maskinlæringsalgoritmer til dynamisk å allokere trafikk til variasjoner som presterer godt, samtidig som det allokeres mindre trafikk til variasjoner som presterer dårlig.

Begrepet "flerarmet banditt" kommer fra et hypotetisk eksperiment der en person må velge mellom flere handlinger (f.eks. spilleautomater, de "enarmede bandittene"), hver med en ukjent utbetaling. Målet er å finne det beste eller mest lønnsomme utfallet gjennom en rekke valg. I begynnelsen av eksperimentet, når oddsen og utbetalingene er ukjente, må spilleren avgjøre hvilken automat han eller hun skal trekke, i hvilken rekkefølge og hvor mange ganger. Dette er "den flerarmede bandittens problem".

Eksempler på flerarmede banditter

Et eksempel fra den virkelige verden på et flerarmet bandittproblem er når et nyhetsnettsted må ta en beslutning om hvilke artikler som skal vises for en besøkende. Uten informasjon om den besøkende er alle klikkutfallene ukjente. Det første spørsmålet er hvilke artikler som vil få flest klikk. Og i hvilken rekkefølge skal de vises? Nettstedets mål er å maksimere engasjementet, men de har mange typer innhold å velge mellom, og de mangler data som kan hjelpe dem med å følge en bestemt strategi.

Nyhetsnettstedet har et lignende problem når det gjelder å velge hvilke annonser som skal vises for de besøkende. I dette tilfellet ønsker de å maksimere annonseinntektene, men de mangler kanskje nok informasjon om de besøkende til å følge en spesifikk annonsestrategi. På samme måte som med nyhetsartikler har de vanligvis et stort antall annonser å velge mellom. Hvilke annonser vil gi størst inntekter for nyhetssiden?

Nettstedet må ta en rekke beslutninger, hver med ukjent utfall og "utbetaling".

Flerarmede bandittløsninger

Det finnes mange ulike løsninger som dataforskere har utviklet for å takle problemet med flerarmede banditter. Nedenfor er en liste over noen av de mest brukte løsningene for flerarmede banditter:

1. Epsilon-greedy

   Dette er en algoritme som kontinuerlig balanserer utforskning og utnyttelse. (I "grådige" eksperimenter trekkes alltid spaken med høyest kjent utbetaling, bortsett fra når en tilfeldig handling utføres). En tilfeldig valgt arm trekkes en brøkdel ε av tiden. De resterende 1ε av gangene trekkes armen med høyest kjent utbetaling.

2. Øvre konfidensgrense

   Denne strategien er basert på prinsippet om optimisme i møte med usikkerhet, og forutsetter at de ukjente gjennomsnittsutbetalingene for hver arm vil være så høye som mulig, basert på observerbare data.

3. Thompson-sampling (bayesiansk)

   Med denne randomiserte strategien for sannsynlighetsmatching skal antall trekk for en gitt spak samsvare med den faktiske sannsynligheten for at den er den optimale spaken.

Hvordan kontekstuelle banditter skiller seg fra standard flerarmede banditter

En kontekstuell banditt er en avansert personaliseringsalgoritme som forbedrer den flerarmede banditt-tilnærmingen ved å innlemme brukerspesifikke data. Mens tradisjonelle flerarmede banditter bidrar til å identifisere vinnervarianter, avgjør kontekstuelle banditter hvilken variant som fungerer best for hver enkelt besøkende.

Med "kontekst" menes besøkerspesifikk informasjon som enhetstype, plassering, tidligere atferd eller kjøpshistorikk. Disse dataene gjør det mulig for maskinlæringsmodellen å ta smartere beslutninger om hvilket innhold som skal vises for å maksimere konverteringer.

Slik fungerer kontekstuelle banditter:

1. Læringsperiode: Modellen starter med 100 % utforskning ved å tilfeldig tildele variasjoner til besøkende for å samle inn ulike data for prediksjoner.
2. Balansering av utforskning og utnyttelse: Når det er samlet inn nok data om de besøkendes atferd, utnytter modellen (serverer tilpassede variasjoner). Den justerer dynamisk utforsknings-/utnyttelsesgraden etter hvert som den mottar flere hendelser.
3. Kontinuerlig tilpasning: Modellen opprettholder en viss utforskning (maksimalt 95 % utnyttelse) for å sikre kontinuerlig læring og unngå å gå glipp av muligheter

I stedet for å lage komplekse målrettingsregler for ulike brukersegmenter manuelt, lærer kontekstuelle banditter automatisk disse relasjonene og serverer den mest relevante opplevelsen til hver besøkende i sanntid. Denne tilnærmingen eliminerer gjetning og gir ekte 1:1-personalisering i stor skala - noe som er avgjørende i dagens konkurranseutsatte miljø der oppmerksomheten er begrenset og forventningene til personalisering er høye.

Den viktigste forskjellen mellom kontekstuelle banditter og tradisjonelle flerarmede banditter er konteksten. Mens standard flerarmede banditter søker en enkelt vinnervariant på tvers av alle brukere, identifiserer kontekstuelle banditter den beste varianten for hver bruker basert på deres spesifikke attributter.

• A/B-testing: Faste trafikksplittinger med valg av en vinner som passer alle
• Flerarmede banditter: Dynamisk trafikkallokering som søker én overordnet "beste" variasjon
• Kontekstuelle banditter: Personaliserte opplevelser basert på brukerkontekst (enhet, plassering, atferd)

Flerarmede banditter vs. A/B-testing

Når du skal bestemme deg for om du skal bruke flerarmede banditter i stedet for A/B-testing, må du avveie avveiningen mellom utnyttelse og utforskning (også kjent som "tjen eller lær").

Nøkkelen til å forstå forskjellen mellom tradisjonell A/B-test og flerarmede banditter er begrepet utnyttelse kontra utforskning:

• Utforskning: Vise ulike varianter til besøkende for å finne ut hvilken som fungerer best
• Utnyttelse: Vise den varianten som gir best resultater for å maksimere konverteringen

Med A/B-testing har du en begrenset periode med ren utforskning, der du allokerer like mye trafikk til versjon A og versjon B. Når du har kåret en vinner, går du over i en lang periode med utnyttelse, der 100 % av brukerne går til den vinnende varianten. Et problem med denne tilnærmingen er at du kaster bort ressurser på den tapende varianten mens du prøver å samle inn data og finne ut hvilken som er vinneren.

Med flerarmede banditter er testene adaptive, og inkluderer perioder med utforskning og utnyttelse samtidig. De flytter trafikken gradvis mot vinnervarianter, i stedet for å tvinge deg til å vente med å kåre en vinner på slutten av et eksperiment. Denne prosessen er raskere og mer effektiv fordi man bruker mindre tid på å sende trafikk til åpenbart dårligere varianter.

En av de største ulempene med flerarmede banditt-tester er at de er svært kompliserte. Det er rett og slett vanskeligere og mer ressurskrevende å kjøre flerarmede banditt-tester.

Metrisk	A/B-testing	Flerarmet banditt
Tid å implementere vinneren	2-4 uker i gjennomsnitt	Kan begynne i løpet av få dager
Nødvendig trafikk	Høyere (fast allokering)	Lavere (adaptiv allokering)
Mulighetskostnad	Høy (veletablerte p-verdier)~5-15 % konverteringstap i løpet av testperioden	~1-5 % konverteringstap i løpet av testperioden
Statistisk stringens	Høy (veletablerte p-verdier)	Moderat (fokuserer på regret-minimering)
Best for testens varighet	Langsiktig (uker/måneder)	Kortsiktig (dager/uker)
Beregningsteknisk kompleksitet	Lav	Moderat til høy

Når bør man bruke flerarmede banditter?

Det finnes noen kjente situasjoner der tester med flerarmede banditter vanligvis fungerer best:

1. Overskrifter og kortsiktige kampanjer: Alternativkostnaden ved å vente på resultatene av A/B-tester gjør bandittalgoritmer til et bedre valg for kortvarig innhold, for eksempel overskriftstester for nye artikler eller feriekampanjer.

2. Langsiktige dynamiske endringer: Når det som testes endres så mye at resultatene av en A/B-test blir ugyldige over tid, er flerarmede banditter et alternativ til å teste gjentatte ganger ved å utforske kontinuerlig.

3. Målretting: Målretting er et annet eksempel på langsiktig bruk av bandittalgoritmer. Hvis visse typer brukere er vanligere enn andre, kan den flerarmede banditten bruke innlærte målrettingsregler raskere for mer vanlige brukere, samtidig som man fortsetter å eksperimentere på mindre vanlige brukere.

4. Automatisering i stor skala: Hvis du har flere komponenter som kontinuerlig skal optimaliseres, gir den flerarmede banditten deg et rammeverk for delvis automatisering av optimaliseringsprosessen for lavrisikoproblemer, som det kan være for kostbart å analysere individuelt.

Når bør man bruke kontekstuelle banditter?

Kontekstuelle banditter gir betydelig forretningsverdi i disse scenariene:

1. Personalisering i stor skala: Når du trenger å tilby virkelig personaliserte opplevelser for hver enkelt bruker i stedet for en standardtilnærming, slik at du kan levere riktig innhold til riktig person til riktig tid.
2. Dynamisk tilpasning: Når du trenger et system som serverer den beste variasjonen i hver økt, selv når brukerpreferansene endrer seg.
3. Eliminering av alternativkostnader: I motsetning til A/B-tester som krever uker eller måneder for å oppnå statistisk signifikans, begynner kontekstuelle banditter å optimalisere umiddelbart, noe som reduserer eksponeringen for underpresterende variasjoner i sanntid.
4. Optimalisering med lite vedlikehold: For sider der innholdet ikke endres for ofte. Etter hvert som tiden går, blir ML-modellen skarpere med dataene den samler inn, noe som gjør dette til en "sett det og glem det"-optimalisering som kan kjøres kontinuerlig.

Slik bruker Optimizely flerarmede banditter

Optimizely Web Experimentation og Feature Experimentation bruker noen få flerarmede bandittalgoritmer til å endre trafikkallokeringen på tvers av variasjoner på en intelligent måte for å oppnå et mål. Avhengig av målet ditt, kan du velge mellom målene:

1. Statistikkakselerator

Finn statistisk signifikante variasjoner så raskt som mulig.

• Reduserer eksperimentets varighet ved å vise flere besøkende den variasjonen som har størst sjanse for å oppnå statistisk signifikans.
• Maksimerer antall lærdommer fra eksperimenter i løpet av en tidsramme, slik at du bruker mindre tid på å vente på resultater.
• Forsøker å oppdage så mange signifikante variasjoner som mulig.

2. Flerarmet banditt (MAB)

Maksimerer belønning og minimerer regret.

• Lar deg utnytte så mye verdi fra den ledende variasjonen som mulig i løpet av eksperimentets livssyklus, slik at du unngår kostnadene ved å vise suboptimale erfaringer.
• Genererer ikke statistisk signifikans.
• Bruker Thompson Sampling-algoritme for binære beregninger.
• Bruker Epsilon-greedy-algoritmen for numeriske beregninger.

3. Kontekstuell banditt

Lever virkelig personaliserte opplevelser.

• Avanserte trebaserte maskinlæringsmodeller som tilpasser opplevelsene til individuelle brukerkontekster
• Gir 1:1 personalisering i stor skala uten manuell segmentering
• Best for å skape varige personaliseringsprogrammer som tilpasser seg endret brukeratferd