De multi-armed bandit is een klassiek probleem in reinforcement learning, waarbij een speler moet kiezen tussen meerdere “armen” (bandit arms) – bijvoorbeeld gokautomaten – elk met een onbekende maar verschillende kans op beloning. Het doel is om de totale beloning te maximaliseren na een bepaald aantal trekkingen. Wat is een bandit in deze context? Een bandit verwijst naar elke arm van de gokautomaat, of met andere woorden, elke keuze die de speler kan maken. Elke bandit levert een willekeurig resultaat met een eigen kansverdeling.
Dit probleem introduceert een dilemma: exploratie versus exploitatie. Exploratie betekent het uitproberen van verschillende bandits om de bandit met de hoogste kans op beloning te vinden. Exploitatie betekent het focussen op de bandit die momenteel het beste lijkt om de beloning te maximaliseren. Het vinden van de juiste balans tussen exploratie en exploitatie staat centraal in het multi-armed bandit probleem.
Wat is een bandit en waarom is dit probleem belangrijk? In de praktijk kunnen veel problemen worden gemodelleerd als een multi-armed bandit probleem. Bijvoorbeeld:
- Online adverteren: Welke banner levert de meeste kliks op? Elke banner is een bandit, het aantal kliks is de beloning.
- Dynamische prijsbepaling: Welke prijs optimaliseert de omzet of winst? Elke prijs is een bandit, de omzet/winst is de beloning.
- Aanbevelingssystemen: Welk product moet aan een gebruiker worden aanbevolen? Elk product is een bandit, de tevredenheid van de gebruiker is de beloning.
- Klinische studies: Welke behandeling is het meest effectief en heeft de minste bijwerkingen? Elke behandeling is een bandit, de effectiviteit van de behandeling is de beloning.
Om het multi-armed bandit probleem op te lossen, zijn er verschillende algoritmen ontwikkeld, elk met een eigen aanpak om de balans tussen exploratie en exploitatie te vinden. Enkele veelgebruikte algoritmen zijn:
- Naïef algoritme: Test elke bandit een vast aantal keren en kies vervolgens de bandit met de hoogste gemiddelde beloning.
- ε-Greedy algoritme: Kies met kans ε een willekeurige bandit voor exploratie; kies met kans 1-ε de bandit met de hoogste gemiddelde beloning voor exploitatie.
- UCB (Upper Confidence Bound) algoritme: Kies de bandit met de hoogste bovengrens van het betrouwbaarheidsinterval, rekening houdend met zowel de gemiddelde beloning als de onzekerheid van de schatting.
- Thompson Sampling algoritme: Gebruik Bayesiaanse kansverdelingen om de beloning van elke bandit te schatten en kies de bandit op basis van de kans dat deze het beste is.
Elk algoritme heeft zijn eigen voor- en nadelen en de effectiviteit ervan hangt af van de specifieke kenmerken van het probleem. Begrijpen wat een bandit is en de bijbehorende algoritmen helpt bij het kiezen van de juiste methode om beslissingen te optimaliseren in onzekere situaties.
Video uitleg over hoe UCB werkt Uitleg UCB Algoritme
De keuze tussen deze algoritmen hangt af van het specifieke probleem en de eisen aan de rekenkracht. Thompson Sampling is bijvoorbeeld vaak effectiever dan UCB in praktische toepassingen met grote datasets en real-time verwerkingseisen.
