Handlingsverdi er et grunnleggende begrep 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 ved å velge aksjon $a$ frem til tidspunkt $t$:

hvor:

• $Q_t(a)$ er estimert verdi for aksjon $a$ ved tid $t$;
• $N_t(a)$ er antall ganger aksjon $a$ har blitt valgt frem til tid $t$;
• $R_i$ er belønningen oppnådd i hvert tilfelle 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å nytt for hvert tidssteg. Med inkrementelle oppdateringer blir dette unødvendig. Formelen for inkrementelle oppdateringer kan utledes slik:

hvor for en gitt handling:

• $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 du kjenner estimatet av den $k$-te belønningen, $Q_k$, og den faktiske $k$-te belønningen, $R_k$, kan du 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 stegstørrelsesparameter 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$, siden det ikke krever ekstra lagringsplass (for å lagre hvor mange ganger en handling er valgt) og tillater tilpasning til ikke-stasjonære miljøer ved å legge større vekt på nyere observasjoner.

Optimistisk initialisering

I begynnelsen av en treningsprosess kan estimatene 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 oppmuntre til 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.