Problemet med multi-armed bandit (MAB) är en välkänd utmaning inom förstärkningsinlärning, beslutsfattande och sannolikhetsteori. Det innebär att en agent upprepade gånger väljer mellan flera handlingar, där varje handling ger en belöning från en viss sannolikhetsfördelning. Målet är att maximera avkastningen under ett givet antal tidssteg.

Problemets ursprung

Uttrycket "multi-armed bandit" kommer från analogin med en enarmad bandit, det vill säga en spelautomat med en spak. I detta scenario kan man tänka sig flera spelautomater, eller en spelautomat med flera spakar (armar), där varje arm är kopplad till en unik sannolikhetsfördelning för belöningar. Målet är att maximera avkastningen under ett begränsat antal försök genom att noggrant välja vilken spak som ska dras.

Utmaningen

MAB-problemet fångar utmaningen i att balansera utforskning och exploatering:

• Utforskning: att prova olika armar för att samla information om deras utbetalningar;
• Exploatering: att dra i den arm som för närvarande verkar bäst för att maximera omedelbara belöningar.

Ett naivt tillvägagångssätt — att spela på en enda arm upprepade gånger — kan leda till suboptimala resultat om det finns en bättre arm som förblir outforskad. Omvänt kan överdriven utforskning slösa resurser på alternativ med låg belöning.

Tillämpningar i verkliga världen

Även om det ursprungligen formulerades inom spel, förekommer MAB-problemet inom många områden:

• Onlineannonsering: välja den bästa annonsen att visa baserat på användarengagemang;
• Kliniska studier: testa flera behandlingar för att hitta den mest effektiva;
• Rekommendationssystem: leverera det mest relevanta innehållet till användare.