Utforska-eller-utnyttja-dilemmat
Varje gång jag går på indisk restaurang ställs jag inför ett dilemma: Ska jag beställa min favorit Tikka Massala eller våga testa något helt nytt från menyn? Många beslut i vår vardag kokar ner till just ett sådant val mellan nytt och beprövat. Ska vi äta lunch på stamstället eller prova nykomligen på hörnet? Ska vi välja en capricciosa eller testa en pizza special? Ska vi ta en tripp till det outforskade, eller boka ännu en charter till Mallorca? I ena vågskålen: det bekanta, välbeprövade. I den andra vågskålen: det ännu oupptäckta.
Att utforska valmöjligheterna i den senare vågskålen ger dig möjlighet att upptäcka nya favoriter, men utsätter dig samtidigt för risken att få något som är sämre än det du redan känner till. Var finns balansen mellan att utforska vilka som är de bästa alternativen, och att utnyttja det du redan har lärt dig om vad du gillar bäst? Det här utforska/utnyttja-dilemmat (eng. explore/exploit) har sysselsatt matematiker och datavetare under den senare halvan av 1900-talet. Dilemmat är inte bara notoriskt svårt att lösa; det har dessutom flera överraskande tillämpningar.
AB-testning
Marknadsföringsinsatser har blivit alltmer digitala. Annonser i papperstidningar och glossiga produktkataloger, har fått stryka på foten för digitala annonser via epost-utskick och webbplatser. Det finns mycket pengar att hämta om man lyckas vara det företag som får flest hemsidesbesökare att sajna upp för ett nyhetsbrev eller genomföra ett köp. Men i kampen om internetkunderna döljer sig ett utforska/utnyttja-dilemma.
Det har visat sig att små detaljer, som typsnitt, färger och formuleringar har oväntat stor betydelse för våra beteenden på nätet. För att avgöra vilken design – till exempel vilken färg på ”köp”-knappen – som gör att användarna handlar på webbplatsen, genomför många företag rutinmässigt statistiska undersökningar. De designar två (eller flera) versioner av sin webbsida – A och B – och visar den ena versionen för en viss andel av sina besökare och den andra versionen för en annan andel. Därefter mäter de hur väl de olika designerna uppfyller sina mål. Processen kallas för AB-testning.
Netflix är ett av företagen som rutinmässigt använder AB-testning för att optimera användarnas upplevelse. Bland annat testar de vilken omslagsbild, som gör användarna mest nyfikna på att se en bestämd serie.
Även Barack Obama’s kampanjteam använde AB-testning inför valet 2008. Bland annat undersökte de vilken av följande knappar som fick flest hemsidesbesökare att sajna upp som medlem.
Det visade sig att ”Learn more” var det mest effektiva alternativet. AB-testningen av hemsidan ökade antalet nya medlemmar med 40 %, och gav uppskattningsvis ca 60 miljoner dollar i ökade donationer.
AB-testning kan alltså vara häpnadsväckande effektivt. Men det finns en hake. Under tiden som experimentet körs, erhålls information om vilken version av webbsidan som fungerar bäst. Att då fortsätta att låta en andel av användarna se den sämre sidan, riskerar att vara en dålig affär. I den bästa av världar skulle man vilja fortsätta undersökningen (utforska), men samtidigt kapitalisera på de lärdomar som samlas in under experimentets gång (utnyttja). En lösning till utforska/utnyttja-dilemmat skulle med andra ord hjälpa företag i jakten på hemsidesbesökare och betalande kunder.
En sådan lösning skulle också kunna rädda liv.
Randomiserade studier
När man vill testa en ny medicinsk behandling brukar man använda så kallade randomiserade studier. Man delar in försökspersonerna i två grupper – en grupp som får den nya behandlingen och en grupp som får standardbehandlingen (eller placebo). Efter att behandlingen har avslutats kan man med hjälp av statistiska test (så kallad hypotestestning) avgöra om den nya behandlingen varit effektiv i jämförelse med standardbehandlingen. Men proceduren föder ett etiskt dilemma.
Låt säga att studien undersöker en ny cancerbehandling. Om man under studiens gång märker att den nya cancerbehandlingen verkar ha klart bättre effekt, borde inte då även patienterna i den andra gruppen få möjlighet till den behandlingen? Att bibehålla uppdelningen av de två grupperna främjar forskningen och följer det statistiska ramverket, men sätter inte patienternas väl i första rummet. Det bästa vore att kunna utforska vilken behandling som är bäst, samtidigt som man utnyttjar lärdomarna som dras under studiens gång. En lösning på utforska/utnyttja-dilemmat skulle alltså kunna rädda liv, men en sådan lösning har visat sig svår att finna.
Strategier
Utforska/utnyttja-dilemmat har visat sig notoriskt svårt att lösa. Än idag finns det inte någon universell, optimal metod. Däremot finns det metoder som löser problemet under vissa förutsättningar. Ett sådant exempel är Gittins index, som du kan läsa mer om i Brian Christians och Tom Griffiths utmärkta bok Algorithms to live by. Här ska vi fokusera på strategier och tankemönster som tar dig en bit på vägen.
Tid
Det första att lägga märke till är att varje lösning till utforska/utnyttja-dilemmat, beror av din tidshorisont. Är den aktuella valsituationen något som du kommer att ställas inför många gånger framöver? Ja, då är det värt att utforska olika alternativ. Har du exempelvis precis anlänt till en ny stad där du ska bo i några månader, så är det väl värt att utforska restaurangutbudet. Ska du åka hem nästa dag? Ja, då är det klokare att välja en trevlig bistro som du redan har provat. Informationen du vinner på att utforska ytterligare en restaurang, har du ju inte tid att dra nytta av fler gånger. Som Brian Christian och Tom Griffith uttrycker det:
”[E]xplore when you will have time to use the resulting knowledge, exploit when you’re ready to cash in.” s. 35
Girig algoritm
Ett enkelt sätt att hantera utforska/utnyttja dilemmat är att använda sig av en så kallad girig algoritm. Antag att du vill optimera ditt sätt att välja semesterresmål. Du vet att du kommer att åka på semester minst en gång om året, så det är värt att ägna lite tid åt att utforska de olika resemöjligheterna. Under ett antal år reser du därför till ett nytt resmål varje semester, totalt n stycken. När det utforskande stadiet är över, är det dags att utnyttja det du har lärt dig. Då väljer du, enligt algoritmen, nio gånger av tio, att besöka din favorit av de n resmålen. Men du lämnar fortfarande lite rum för utforskande. Var tionde semester väljer du ett resmål som du aldrig har besökt förut. Algoritmen är girig i den meningen att den i de allra flesta fall väljer det dittills allra bästa alternativet.
Zelens algoritm
En annan metod för att hantera utforska/utnyttja-dilemmat utformades av biostatistikern Marvin Zelen. Han plågades av att traditionella randomiserade studier kunde leda till att man undanhöll patienter en visserligen obeprövad, men möjligtvis livräddande, behandling. I stället för att dela upp patienterna i två grupper, föreslog han att man skulle välja vilken behandling som skulle erbjudas en patient enligt en sannolikhetsmodell. Man kan likna Zelens algoritm vid att dra kulor ur en urna.
Vid första dragningen finns två kulor i urnan, en för var och en av de två behandlingsmetoderna. Det är alltså 50 % chans att patienten tilldelas endera behandling. Om den valda behandlingen lyckas, läggs ytterligare en sådan kula i urnan. Det gör att sannolikheten att nästa patient får den behandlingen är 2/3. Om behandlingen misslyckas, läggs i stället en kula för den andra behandlingen i urnan. På så sätt gör Zelens algoritm att det blir mer sannolikt att man tilldelar varje patient den behandling som har störst effekt.
Sexton år senare sattes Zelens idéer i verket. Man ville jämföra två behandlingar för nyfödda barn som behövde hjälp att andas – en ny behandling och en konventionell. Den nya behandlingen var en modifierad hjärt-lung-maskin, en så kallad ECMO-maskin, som vid tidpunkten för studien var en kontroversiell behandling. Ett nyfött barn behandlades med den konventionella metoden och dog. Elva spädbarn i rad tilldelades sedan ECMO-behandlingen, och överlevde. Trots det gynnsamma utfallet fick studien kritik. Det blev nämligen för få spädbarn som behandlades med den konventionella metoden för att det skulle kunna utgöra ett meningsfullt jämförelseunderlag.
På 1990-talet i Storbritannien genomfördes ytterligare en studie. Denna gång var det en traditionellt randomiserad studie. Totalt 200 spädbarn delades upp i två grupper, som var och en fick en av behandlingarna. Även denna studie visade fördelar med ECMO-behandlingen, men för den kunskapen fick man betala ett högt pris. I gruppen som fick den konventionella behandlingen dog 24 fler barn, jämfört med barnen som behandlades med ECMO.
Tiden som vägvisare
Utforska/Utnyttja-dilemmat dyker upp i många olika skepnader. Det finns i företagens AB-testning och forskarnas läkemedelsstudier. Det finns i din vardag när du väljer pizza på pizzerian, försöker hitta det optimala resmålet eller väljer ut vilken bok du ska läsa härnäst. Ska du välja ett beprövat kort, eller våga testa något nytt? Dilemmat har ingen entydig, optimal lösning, även om det finns ett antal mer eller mindre effektiva algoritmer. Den kanske viktigaste lärdomen är kanske ändå att tiden är din vägvisare. När du är ung och har hela livet framför dig – utforska! När du närmar dig ålderns höst, är det dags att utnyttja allt det du har lärt dig. Att vara fast i dina vanor som gammal, är med andra ord helt i sin matematiska ordning.
Referenser och vidare läsning
Christian, Brian & Griffiths, Tom (2016) Algorithms to live by. The computer science of human decisions. Picador.
Cohen, Jonathan, D et al (2007) Should I stay or should I go? How the human brain manages the trade-off between exploitation and exploration. Philos Trans R Soc Lond B Biol Sci. 2007 May 29; 362(1481): 933–942
Masum, Mohammad (2020) Intro to Reinforcement Learning: The Explore-Exploit Dilemma
Netflix technology blog (2016) Selecting the best artwork for videos through A/B testing
Goodman, Rio & Goel, Ashish (2009) Goodman Lecture 5: Uncertainty
Siroker, Dan, How Obama Raised $60 Million by Running a Simple Experiment
Weng, Lilian (2018) The Multi-Armed Bandit Problem and Its Solutions.
Wikipedia, Multi-armed bandit