Multi-armed bandit

Hva er multi-armed bandit-problemet?

I markedsføringstermer er en multi-armed bandit-løsning 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 den allokerer mindre trafikk til variasjoner som underpresterer.

Begrepet «multi-armed bandit» stammer fra et hypotetisk eksperiment der en person må velge mellom flere handlinger (dvs. spilleautomater, de såkalte «one-armed bandits»), hver med en ukjent utbetaling. Målet er å finne det beste eller mest lønnsomme utfallet gjennom en serie valg. I begynnelsen av eksperimentet, når odds og utbetalinger er ukjente, må spilleren bestemme hvilken maskin som skal brukes, i hvilken rekkefølge og hvor mange ganger. Dette er «multi-armed bandit-problemet».

Eksempler på multi-armed bandit

Et eksempel fra virkeligheten på et multi-armed bandit-problem er når et nyhetsnettsted må bestemme hvilke artikler som skal vises til en besøkende. Uten informasjon om den besøkende er alle klikkutfall ukjente. Det første spørsmålet er: hvilke artikler vil få flest klikk? Og i hvilken rekkefølge bør de vises? Nettstedets mål er å maksimere engasjement, men de har mange innholdselementer å velge mellom, og de mangler data som kan hjelpe dem med å følge en spesifikk strategi.

Nyhetsnettstedet har et lignende problem når det skal velge hvilke annonser som skal vises til besøkende. I dette tilfellet ønsker de å maksimere annonseinntektene, men de kan mangle nok informasjon om den besøkende til å følge en spesifikk annonsestrategi. I likhet med problemet med nyhetsartikler har de vanligvis et stort antall annonser å velge mellom. Hvilke annonser vil gi maksimal inntekt for nyhetsnettstedet?

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

Multi-armed bandit-løsninger

Det finnes mange ulike løsninger som informatikere har utviklet for å takle multi-armed bandit-problemet. Nedenfor er en liste over noen av de mest brukte multi-armed bandit-løsningene:

1. Epsilon-greedy

   Dette er en algoritme for kontinuerlig balansering av utforskning og utnyttelse. (I «greedy»-eksperimenter velges alltid spaken med høyest kjent utbetaling, bortsett fra når en tilfeldig handling utføres). En tilfeldig valgt arm trekkes en andel ε av tiden. Resten av tiden (1-ε) trekkes armen med høyest kjent utbetaling.

2. Upper confidence bound

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

3. Thompson Sampling (Bayesiansk)

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

Hvordan contextual bandits skiller seg fra standard multi-armed bandits

En contextual bandit er en avansert personaliseringsalgoritme som forbedrer multi-armed bandit-tilnærmingen ved å inkludere brukerspesifikke data. Mens tradisjonelle multi-armed bandits hjelper med å identifisere vinnende variasjoner, avgjør contextual bandits hvilken variasjon som fungerer best for hver enkelt besøkende.

«Konteksten» refererer til besøkendespesifikk 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 contextual bandits:

1. Læringsperiode: Modellen starter med 100 % utforskning og tildeler variasjoner tilfeldig til besøkende for å samle inn mangfoldige data til prediksjoner.
2. Balansering av utforskning og utnyttelse: Når nok atferdsdata fra besøkende er samlet inn, utnytter modellen (ved å levere personaliserte variasjoner). Den justerer dynamisk forholdet mellom utforskning og utnyttelse etter hvert som den mottar flere hendelser.
3. Kontinuerlig tilpasning: Modellen opprettholder en viss grad av utforskning (maksimalt 95 % utnyttelse) for å sikre kontinuerlig læring og unngå tapte muligheter.

I stedet for å manuelt opprette komplekse målrettingsregler for ulike brukersegmenter, lærer contextual bandits automatisk disse sammenhengene og leverer den mest relevante opplevelsen til hver besøkende i sanntid. Denne tilnærmingen eliminerer gjetting og leverer ekte 1:1-personalisering i stor skala – avgjørende i dagens konkurranseutsatte miljø der oppmerksomhetsspenn er begrenset og forventningene til personalisering er høye.

Hovedforskjellen mellom contextual bandits og tradisjonelle multi-armed bandits er kontekst. Mens standard multi-armed bandits søker én vinnende variasjon på tvers av alle brukere, identifiserer contextual bandits den beste variasjonen for hver bruker basert på deres spesifikke egenskaper.

• A/B-testing: Faste trafikkfordelinger med én vinner for alle
• Multi-armed bandits: Dynamisk trafikkallokering som søker én overordnet «beste» variasjon
• Contextual bandits: Personaliserte opplevelser basert på brukerkontekst (enhet, plassering, atferd)

Multi-armed bandits vs. A/B-testing

Når du skal avgjøre om du skal bruke multi-armed bandits i stedet for A/B-testing, må du veie avveiningen mellom utnyttelse og utforskning (noen ganger kjent som «tjene eller lære»).

Nøkkelen til å forstå forskjellen mellom tradisjonell A/B-testing og multi-armed bandits er konseptet utnyttelse versus utforskning:

• Utforskning: Vise ulike variasjoner til besøkende for å lære hvilken som presterer best
• Utnyttelse: Vise den best presterende variasjonen for å maksimere konverteringer

Med A/B-testing har du en begrenset periode med ren utforskning der du fordeler trafikk likt mellom Versjon A og Versjon B. Når du erklærer en vinner, går du over til en lang periode med utnyttelse, der 100 % av brukerne sendes til den vinnende variasjonen. Et problem med denne tilnærmingen er at du bruker ressurser på den tapende variasjonen mens du prøver å samle data og finne ut hvilken som er vinneren.

Med multi-armed bandit-testing er testene adaptive og inkluderer perioder med utforskning og utnyttelse samtidig. De flytter trafikk gradvis mot vinnende variasjoner, i stedet for å tvinge deg til å vente med å erklære en vinner ved slutten av et eksperiment. Denne prosessen er raskere og mer effektiv fordi mindre tid brukes på å sende trafikk til åpenbart dårligere variasjoner.

En av de viktigste ulempene med multi-armed bandit-testing er den beregningsmessige kompleksiteten. Enkelt sagt er det mer krevende og ressursintensivt å kjøre multi-armed bandit-tester.

Når bør du bruke multi-armed bandits

Det finnes noen kjente situasjoner der multi-armed bandit-testing vanligvis fungerer best:

1. Overskrifter og kortsiktige kampanjer: Alternativkostnaden ved å vente på resultatene av A/B-tester gjør bandit-algoritmer til et bedre valg for kortvarig innhold som overskriftstesting for nye artikler eller høytidskampanjer.

2. Langsiktige dynamiske endringer: Når elementet som testes endrer seg nok til å ugyldiggjøre resultatene av en A/B-test over tid, gir multi-armed bandits et alternativ til gjentatt retesting ved å utforske kontinuerlig.

3. Målretting: Målretting er et annet eksempel på langsiktig bruk av bandit-algoritmer. Hvis visse typer brukere er mer vanlige enn andre, kan multi-armed bandit-algoritmen anvende lærte målrettingsregler raskere for mer vanlige brukere, samtidig som den fortsetter å eksperimentere med mindre vanlige brukere.

4. Automatisering for skalerbarhet: Hvis du har flere komponenter som skal optimaliseres kontinuerlig, gir multi-armed bandit-tilnærmingen deg et rammeverk for delvis automatisering av optimaliseringsprosessen for lavrisikoproblemer, som kan være for kostbare å analysere individuelt.

Når bør du bruke contextual bandits

Contextual bandits leverer betydelig forretningsverdi i disse scenarioene:

1. Personalisering i stor skala: Når du trenger å levere virkelig personaliserte opplevelser for hver bruker i stedet for én-løsning-for-alle-tilnærminger, og levere riktig innhold til riktig person til riktig tid.
2. Dynamisk tilpasning: Når du trenger et system som leverer den beste variasjonen i hver økt, selv etter hvert som brukerpreferansene utvikler seg.
3. Eliminering av alternativkostnader: I motsetning til A/B-tester som krever uker eller måneder for å oppnå statistisk signifikans, begynner contextual bandits å 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 opp og glem det»-optimalisering som kan kjøre kontinuerlig.

Hvordan Optimizely bruker multi-armed bandits

Optimizely Web Experimentation og Feature Experimentation bruker flere multi-armed bandit-algoritmer for å intelligent endre trafikkfordelingen mellom variasjoner for å oppnå et mål. Avhengig av målet ditt velger du mellom følgende mål:

1. Stats Accelerator

Finn en statistisk signifikant variasjon så raskt som mulig.

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

2. Multi-armed bandit (MAB)

Maksimer gevinst og minimer tap.

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

3. Contextual bandit

Lever virkelig personaliserte opplevelser.

• Avanserte trebaserte maskinlæringsmodeller som matcher opplevelser til individuelle brukerkontekster
• Gir 1:1-personalisering i stor skala uten manuell segmentering
• Best egnet for å skape varige personaliseringsprogrammer som tilpasser seg endrede brukeratferder