Multi-armed bandit (MAB)-problemet er en velkjent utfordring innenfor forsterkende læring, beslutningstaking og sannsynlighetsteori. Det innebærer at en agent gjentatte ganger velger mellom flere handlinger, hvor hver handling gir en belønning fra en fast sannsynlighetsfordeling. Målet er å maksimere avkastningen over et gitt antall tidssteg.

Problemets opprinnelse

Begrepet "multi-armed bandit" stammer fra analogien til en spilleautomat, ofte kalt en "one-armed bandit" på grunn av spaken. I dette scenariet kan man tenke seg flere spilleautomater, eller en spilleautomat med flere spaker (armer), hvor hver arm er tilknyttet en unik sannsynlighetsfordeling for belønning. Målet er å maksimere avkastningen over et begrenset antall forsøk ved nøye å velge hvilken spak som skal trekkes.

Utfordringen

MAB-problemet illustrerer utfordringen med å balansere utforskning og utnyttelse:

• Utforskning: prøve ulike armer for å samle informasjon om deres utbetalinger;
• Utnyttelse: trekke i den armen som for øyeblikket virker best for å maksimere umiddelbare gevinster.

En naiv tilnærming — å spille på én arm gjentatte ganger — kan føre til suboptimale resultater dersom en bedre arm finnes, men forblir uutforsket. På den annen side kan overdreven utforskning sløse ressurser på alternativer med lav gevinst.

Virkelige applikasjoner

Selv om det opprinnelig ble formulert innen pengespill, forekommer MAB-problemet i mange fagfelt:

• Nettannonsering: valg av den beste annonsen å vise basert på brukerengasjement;
• Kliniske studier: utprøving av flere behandlinger for å finne den mest effektive;
• Anbefalingssystemer: presentasjon av det mest relevante innholdet til brukere.