Multi-armed bandit (MAB) -ongelma on tunnettu haaste vahvistusoppimisessa, päätöksenteossa ja todennäköisyysteoriassa. Siinä agentti valitsee toistuvasti useiden toimintojen välillä, joista jokainen tarjoaa palkkion jostakin kiinteästä todennäköisyysjakaumasta. Tavoitteena on maksimoida tuotto ennalta määrätyn aikajakson aikana.

Ongelman alkuperä

Termi "multi-armed bandit" juontaa juurensa analogiasta kolikkopeliin, jota kutsutaan usein "yksikätiseksi rosvoksi" sen vivun vuoksi. Tässä tilanteessa kuvitellaan, että käytössä on useita kolikkopelejä tai kolikkopeli, jossa on useita vipuja (käsivarsia), ja jokainen vipu liittyy erilliseen todennäköisyysjakaumaan palkkioiden suhteen. Tavoitteena on maksimoida tuotto rajallisen yritysmäärän aikana valitsemalla huolellisesti, mitä vipua vetää.

Haaste

MAB-ongelma kuvaa tasapainottelun haastetta etsinnän ja hyödyntämisen välillä:

• Etsintä: eri vipujen kokeileminen tietojen keräämiseksi niiden tuotoista;
• Hyödyntäminen: sen vivun vetäminen, joka vaikuttaa tällä hetkellä parhaalta välittömien palkkioiden maksimoimiseksi.

Naivi lähestymistapa — yhden vivun toistuva pelaaminen — voi johtaa epäoptimaalisiin tuottoihin, jos parempi vipu jää tutkimatta. Toisaalta liiallinen etsintä voi tuhlata resursseja matalan tuoton vaihtoehtoihin.

Reaali­elämän sovellukset

Vaikka MAB-ongelma alun perin kehitettiin uhkapelaamiseen, se esiintyy monilla aloilla:

• Verkkomainonta: parhaan mainoksen valinta käyttäjän sitoutumisen perusteella;
• Kliiniset kokeet: useiden hoitojen testaaminen tehokkaimman löytämiseksi;
• Suositusjärjestelmät: käyttäjille merkityksellisimmän sisällön tarjoaminen.