Summary  
This chapter covers the programming concept of the multi-armed bandit algorithm, illustrating how to implement a decision-making strategy that balances exploration and exploitation to maximize cumulative rewards from actions with unknown probability distributions.

General domain of usage  
Online advertising

**Multi-armed bandit (MAB)-problemet** er en kjent 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 fast antall **tidssteg**.

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 se for seg **flere spilleautomater**, eller en spilleautomat med **flere spaker (armer)**, hvor hver arm er knyttet til en **unik sannsynlighetsfordeling** for belønninger. Målet er å **maksimere avkastningen** over et begrenset antall forsøk ved nøye å velge hvilken spak som skal trekkes.

**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 belønninger.

En **naiv tilnærming** — å spille på én arm gjentatte ganger — kan føre til **suboptimale gevinster** hvis en bedre arm finnes, men ikke blir utforsket. På den annen side kan **overdreven utforskning** **sløse ressurser** på alternativer med lav belønning.

Selv om det opprinnelig ble formulert innen pengespill, dukker **MAB-problemet** opp i **mange felt**:
- **Nettannonsering**: valg av beste annonse å vise basert på brukerengasjement;
- **Kliniske studier**: testing av flere behandlinger for å finne den mest effektive;
- **Anbefalingssystemer**: vise det mest relevante innholdet til brukere.

Hva er den viktigste utfordringen i multi-armed bandit-problemet?

Reinforcement Learning (RL) er en kraftig gren av maskinlæring som fokuserer på å trene intelligente agenter gjennom interaksjon med sitt miljø. I dette kurset lærer du hvordan agenter gradvis oppdager effektive atferder gjennom prøving og feiling. Du starter med grunnleggende konsepter som Markov beslutningsprosesser og multi-armede banditter, og fortsetter med dynamisk programmering, Monte Carlo-metoder og temporal difference-læring.

Lær hvordan man trener agenter til å ta optimale beslutninger gjennom prøving og feiling. Utforsk det grunnleggende innenfor teori om forsterkende læring. Få praktisk erfaring med å sette opp og kjøre et Gymnasium-miljø.

Forstå utforskning-utnyttelse-avveiningen gjennom multi-armet bandittproblem. Implementering av handlingsverdiestimering, ε-grådig, øvre konfidensgrense og gradient-bandittmetoder. Evaluering av algoritmers ytelse på simulerte belønningsmaksimeringsoppgaver.

Behersk dynamisk programmering for modellbasert RL. Oppdag hvordan Bellman-likninger kan brukes til å evaluere og forbedre policyer. Implementering av policy- og verdiiterasjonsalgoritmer. Utforsk generalisert policyiterasjon som det teoretiske grunnlaget for modellfrie metoder.

Behersk Monte Carlo-metoder for modellfri RL. Estimer verdifunksjoner og utled optimale policyer fra fullstendige episoder. Implementer on-policy og off-policy Monte Carlo-kontrollalgoritmer. Utforsk strategier for utforskning for å optimalisere modellfri læring.

Behersk temporal difference-læring for modellfri RL. Estimeringsmetoder for verdifunksjoner fra delvise episoder ved bruk av TD(0)-oppdateringer. Implementering av on-policy SARSA og off-policy Q-Learning-algoritmer. Utforsk hvordan Monte Carlo-metoder og TD-læring kombineres i n-trinns TD og TD(λ).

Probleminnledning

Opprinnelse til problemet

Utfordringen

Virkelige applikasjoner