Multi-armed bandit (MAB)-problemet er en velkendt udfordring inden for reinforcement learning, beslutningstagning og sandsynlighedsteori. Det indebærer, at en agent gentagne gange vælger mellem flere handlinger, hvor hver handling giver en belønning fra en fast sandsynlighedsfordeling. Målet er at maksimere afkastet over et fast antal tidsintervaller.

Oprindelse af problemet

Udtrykket "multi-armed bandit" stammer fra analogien til en spilleautomat, ofte kaldet en "one-armed bandit" på grund af dens håndtag. I dette scenarie kan man forestille sig flere spilleautomater eller en spilleautomat med flere håndtag (arme), hvor hver arm er forbundet med en særskilt sandsynlighedsfordeling for belønninger. Målet er at maksimere afkastet over et begrænset antal forsøg ved omhyggeligt at vælge, hvilket håndtag der skal trækkes i.

Udfordringen

MAB-problemet illustrerer udfordringen ved at balancere udforskning og udnyttelse:

• Udforskning: afprøvning af forskellige arme for at indsamle information om deres udbetalinger;
• Udnyttelse: valg af den arm, der aktuelt ser bedst ud, for at maksimere den umiddelbare belønning.

En naiv tilgang — at spille den samme arm gentagne gange — kan føre til suboptimale resultater, hvis en bedre arm findes, men forbliver uafprøvet. Omvendt kan overdreven udforskning spilde ressourcer på muligheder med lav belønning.

Virkelige anvendelser

Selvom det oprindeligt blev formuleret inden for gambling, optræder MAB-problemet i mange felter:

• Online annoncering: valg af den bedste annonce at vise baseret på brugerengagement;
• Kliniske forsøg: afprøvning af flere behandlinger for at finde den mest effektive;
• Anbefalingssystemer: præsentation af det mest relevante indhold for brugere.