Handlingsverdi er et grunnleggende konsept i MAB-problemet. Det spiller en sentral rolle i ulike algoritmer, inkludert epsilon-grådig og øvre konfidensgrense. Hovedformålet med en handlingsverdi er å gi et estimat på den forventede belønningen når en spesifikk handling velges. Det ligner på en tilstands-handlingsverdi, men er uavhengig av tilstand på grunn av den tilstandsløse naturen til MAB-problemet.

Definisjon av handlingsverdi

Formelt representerer handlingsverdien, betegnet som $Q(a)$, den forventede belønningen ved å velge handling $a$:

hvor:

• $R$ er mottatt belønning;
• $A$ er valgt handling.

Siden den sanne belønningsfordelingen vanligvis er ukjent, må vi estimere $Q(a)$ ved hjelp av observerte data.

Estimering av aksjonsverdier

Det finnes flere metoder for å estimere $Q(a)$ basert på observerte belønninger. Den vanligste metoden er gjennomsnittlig prøveestimat, som beregner gjennomsnittlig belønning mottatt fra å velge aksjon $a$ frem til tidspunkt $t$:

hvor:

• $Q_t(a)$ er estimert verdi for aksjon $a$ ved tidssteg $t$;
• $N_t(a)$ er antall ganger aksjon $a$ har blitt valgt frem til tidspunkt $t$;
• $R_i$ er belønningen oppnådd i hver forekomst når aksjon $a$ ble valgt.

Når flere prøver samles inn, vil dette estimatet konvergere mot den sanne forventede belønningen $Q_*(a)$ forutsatt at belønningsfordelingen forblir stasjonær.

Inkrementell oppdateringsregel

Selv om formelen ovenfor kan brukes til å estimere aksjonsverdier, krever den at alle tidligere belønninger lagres, og at summen deres beregnes på hvert tidspunkt. Med inkrementelle oppdateringer blir dette unødvendig. Formelen for inkrementelle oppdateringer kan utledes slik:

hvor for en gitt aksjon:

• $Q_k$ er et estimat av den $k$-te belønningen, som kan uttrykkes som et gjennomsnitt av de første $k-1$ belønningene;
• $R_k$ er den faktiske $k$-te belønningen.

Intuisjon

Når man kjenner estimatet av den $k$-te belønningen, $Q_k$, og den faktiske $k$-te belønningen, $R_k$, kan man måle feilen som forskjellen mellom disse verdiene. Deretter kan neste estimat beregnes ved å justere det forrige estimatet litt i retning av den faktiske belønningen, for å redusere feilen.

Denne intuisjonen leder til en annen formel, som ser slik ut:

hvor $\alpha$ er en steglengdeparameter som styrer læringshastigheten. Som i den forrige formelen kan alfa være $\frac1k$, og det vil gi et gjennomsnittlig estimat. Alternativt brukes ofte en konstant $\alpha$, da dette ikke krever ekstra lagringsplass (for å lagre hvor mange ganger en aksjon er valgt) og tillater tilpasning til ikke-stasjonære miljøer ved å legge større vekt på nyere observasjoner.

Optimistisk initialisering

Ved starten av en treningsprosess kan estimater for handlingsverdier variere betydelig, noe som kan føre til for tidlig utnyttelse. Dette innebærer at agenten kan utnytte sin innledende kunnskap for tidlig, og dermed favorisere suboptimale handlinger basert på begrenset erfaring. For å motvirke dette og fremme innledende utforskning, er en enkel og effektiv teknikk optimistisk initialisering.

Ved optimistisk initialisering blir handlingsverdiene satt til relativt høye verdier (for eksempel $Q_0(a) = 1$ i stedet for 0). Denne tilnærmingen gir inntrykk av at alle handlinger er lovende i starten. Som et resultat blir agenten motivert til å utforske hver handling flere ganger før den velger det beste alternativet. Denne teknikken er mest effektiv når den brukes sammen med konstant steg-størrelse.