Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.
Lære Aktionsværdier | Multi-Armed Bandit Problem
Introduktion til Forstærkningslæring

bookAktionsværdier

Handlingsværdi er et grundlæggende begreb i MAB-problemet. Det spiller en central rolle i forskellige algoritmer, herunder epsilon-greedy og upper confidence bound. Hovedformålet med en handlingsværdi er at give et estimat af den forventede belønning, når en bestemt handling vælges. Det ligner en tilstands-handlingsværdi, men er uafhængig af en tilstand på grund af MAB-problemets tilstandsløse karakter.

Definition af handlingsværdi

Formelt repræsenterer handlingsværdien, betegnet som Q(a)Q(a), den forventede belønning ved at vælge handling aa:

Q(a)=E[RA=a]\def\E{\operatorname{\mathbb{E}}} Q(a) = \E[R | A = a]

hvor:

  • RR er den modtagne belønning;
  • AA er den valgte handling.

Da den sande belønningsfordeling typisk er ukendt, skal vi estimere Q(a)Q(a) ved hjælp af observerede data.

Estimering af handlingsværdier

Der findes flere metoder til at estimere Q(a)Q(a) baseret på observerede belønninger. Den mest almindelige metode er gennemsnitsestimatet, som beregner den gennemsnitlige belønning opnået ved at vælge handling aa indtil tidspunkt tt:

Qt(a)=R1+R2+...+RNt(a)Nt(a)=i=1Nt(a)RiNt(a)Q_t(a) = \frac{R_1 + R_2 + ... + R_{N_t(a)}}{N_t(a)} = \frac{\sum_{i=1}^{N_t(a)} R_i}{N_t(a)}

hvor:

  • Qt(a)Q_t(a) er den estimerede værdi af handling aa ved tidssteg tt;
  • Nt(a)N_t(a) er antallet af gange handling aa er blevet valgt indtil tidspunkt tt;
  • RiR_i er belønningen opnået i hver forekomst, hvor handling aa blev valgt.

Når flere prøver indsamles, konvergerer dette estimat mod den sande forventede belønning Q(a)Q_*(a), forudsat at belønningsfordelingen forbliver stationær.

Note
Definition

En stationær fordeling er en fordeling, der ikke ændrer sig over tid, uanset hvilke handlinger der vælges eller hvordan miljøet ændrer sig.

Inkrementel opdateringsregel

Selvom ovenstående formel kan bruges til at estimere handlingsværdier, kræver den lagring af alle tidligere belønninger og genberegning af deres sum ved hvert tidssteg. Med inkrementelle opdateringer bliver dette unødvendigt. Formlen for inkrementelle opdateringer kan udledes således:

Qk+1=1ki=1kRi=1k(Rk+i=1k1Ri)=1k(Rk+(k1)Qk)=1k(Rk+kQkQk)=Qk+1k(RkQk)\begin{aligned} Q_{k+1} &= \frac1k \sum_{i=1}^k R_i\\ &= \frac1k (R_k + \sum_{i=1}^{k-1} R_i)\\ &= \frac1k (R_k + (k-1) Q_k)\\ &= \frac1k (R_k + k Q_k - Q_k)\\ &= Q_k + \frac1k(R_k - Q_k) \end{aligned}

hvor for en given handling:

  • QkQ_k er et estimat af den kk-te belønning, som kan udtrykkes som gennemsnittet af de første k1k-1 belønninger;
  • RkR_k er den faktiske kk-te belønning.

Intuition

Når man kender estimatet af den kk-te belønning, QkQ_k, og den faktiske kk-te belønning, RkR_k, kan fejlen måles som forskellen mellem disse værdier. Derefter kan det næste estimat beregnes ved at justere det forrige estimat en smule i retning af den faktiske belønning for at reducere fejlen.

Denne intuition fører til en anden formel, som ser således ud:

Qk+1=Qk+α(RkQk)Q_{k+1} = Q_k + \alpha (R_k - Q_k)

hvor α\alpha er en trin-størrelsesparameter, der styrer indlæringshastigheden. Ligesom i den forrige formel kan alpha være 1k\frac1k, hvilket vil resultere i et stikprøvegennemsnit. Alternativt anvendes ofte en konstant α\alpha, da det ikke kræver ekstra plads (til at gemme hvor mange gange en handling er valgt) og muliggør tilpasning til ikke-stationære miljøer ved at lægge større vægt på nylige observationer.

Optimistisk initialisering

I begyndelsen af en træningsproces kan estimaterne for handlingsværdier variere betydeligt, hvilket kan føre til for tidlig udnyttelse. Dette betyder, at agenten kan udnytte sin indledende viden for tidligt og favorisere suboptimale handlinger baseret på begrænset erfaring. For at afbøde dette problem og fremme indledende udforskning er en enkel og effektiv teknik optimistisk initialisering.

Ved optimistisk initialisering initialiseres handlingsværdier til relativt høje værdier (f.eks. Q0(a)=1Q_0(a) = 1 i stedet for 0). Denne tilgang skaber indtrykket af, at alle handlinger er indledningsvist lovende. Som resultat motiveres agenten til at udforske hver handling flere gange, før den vælger det bedste valg. Denne teknik er mest effektiv, når den anvendes sammen med konstant trin-størrelse.

Note
Bemærk

Den optimale handlingsrate i denne og fremtidige grafer refererer til andelen af miljøer, hvor den optimale handling blev valgt på et givent tidspunkt.

For eksempel, hvis der er 10 testmiljøer, og den optimale handling blev valgt i 6 af dem ved tidssteg 200, vil den optimale handlingsrate for dette tidssteg være 0.6. Denne måling er nyttig til at evaluere præstation, fordi den korrelerer med maksimering af belønning uden at afhænge af de præcise belønningsværdier.

question mark

Hvad bruges gennemsnitsestimatet til i estimering af handlingsværdier?

Select the correct answer

Var alt klart?

Hvordan kan vi forbedre det?

Tak for dine kommentarer!

Sektion 2. Kapitel 2

Spørg AI

expand

Spørg AI

ChatGPT

Spørg om hvad som helst eller prøv et af de foreslåede spørgsmål for at starte vores chat

Suggested prompts:

Can you explain more about the difference between sample average and incremental update methods?

How does optimistic initialization affect the exploration-exploitation tradeoff?

What are some practical scenarios where constant step-size is preferred over sample average?

Awesome!

Completion rate improved to 2.7

bookAktionsværdier

Stryg for at vise menuen

Handlingsværdi er et grundlæggende begreb i MAB-problemet. Det spiller en central rolle i forskellige algoritmer, herunder epsilon-greedy og upper confidence bound. Hovedformålet med en handlingsværdi er at give et estimat af den forventede belønning, når en bestemt handling vælges. Det ligner en tilstands-handlingsværdi, men er uafhængig af en tilstand på grund af MAB-problemets tilstandsløse karakter.

Definition af handlingsværdi

Formelt repræsenterer handlingsværdien, betegnet som Q(a)Q(a), den forventede belønning ved at vælge handling aa:

Q(a)=E[RA=a]\def\E{\operatorname{\mathbb{E}}} Q(a) = \E[R | A = a]

hvor:

  • RR er den modtagne belønning;
  • AA er den valgte handling.

Da den sande belønningsfordeling typisk er ukendt, skal vi estimere Q(a)Q(a) ved hjælp af observerede data.

Estimering af handlingsværdier

Der findes flere metoder til at estimere Q(a)Q(a) baseret på observerede belønninger. Den mest almindelige metode er gennemsnitsestimatet, som beregner den gennemsnitlige belønning opnået ved at vælge handling aa indtil tidspunkt tt:

Qt(a)=R1+R2+...+RNt(a)Nt(a)=i=1Nt(a)RiNt(a)Q_t(a) = \frac{R_1 + R_2 + ... + R_{N_t(a)}}{N_t(a)} = \frac{\sum_{i=1}^{N_t(a)} R_i}{N_t(a)}

hvor:

  • Qt(a)Q_t(a) er den estimerede værdi af handling aa ved tidssteg tt;
  • Nt(a)N_t(a) er antallet af gange handling aa er blevet valgt indtil tidspunkt tt;
  • RiR_i er belønningen opnået i hver forekomst, hvor handling aa blev valgt.

Når flere prøver indsamles, konvergerer dette estimat mod den sande forventede belønning Q(a)Q_*(a), forudsat at belønningsfordelingen forbliver stationær.

Note
Definition

En stationær fordeling er en fordeling, der ikke ændrer sig over tid, uanset hvilke handlinger der vælges eller hvordan miljøet ændrer sig.

Inkrementel opdateringsregel

Selvom ovenstående formel kan bruges til at estimere handlingsværdier, kræver den lagring af alle tidligere belønninger og genberegning af deres sum ved hvert tidssteg. Med inkrementelle opdateringer bliver dette unødvendigt. Formlen for inkrementelle opdateringer kan udledes således:

Qk+1=1ki=1kRi=1k(Rk+i=1k1Ri)=1k(Rk+(k1)Qk)=1k(Rk+kQkQk)=Qk+1k(RkQk)\begin{aligned} Q_{k+1} &= \frac1k \sum_{i=1}^k R_i\\ &= \frac1k (R_k + \sum_{i=1}^{k-1} R_i)\\ &= \frac1k (R_k + (k-1) Q_k)\\ &= \frac1k (R_k + k Q_k - Q_k)\\ &= Q_k + \frac1k(R_k - Q_k) \end{aligned}

hvor for en given handling:

  • QkQ_k er et estimat af den kk-te belønning, som kan udtrykkes som gennemsnittet af de første k1k-1 belønninger;
  • RkR_k er den faktiske kk-te belønning.

Intuition

Når man kender estimatet af den kk-te belønning, QkQ_k, og den faktiske kk-te belønning, RkR_k, kan fejlen måles som forskellen mellem disse værdier. Derefter kan det næste estimat beregnes ved at justere det forrige estimat en smule i retning af den faktiske belønning for at reducere fejlen.

Denne intuition fører til en anden formel, som ser således ud:

Qk+1=Qk+α(RkQk)Q_{k+1} = Q_k + \alpha (R_k - Q_k)

hvor α\alpha er en trin-størrelsesparameter, der styrer indlæringshastigheden. Ligesom i den forrige formel kan alpha være 1k\frac1k, hvilket vil resultere i et stikprøvegennemsnit. Alternativt anvendes ofte en konstant α\alpha, da det ikke kræver ekstra plads (til at gemme hvor mange gange en handling er valgt) og muliggør tilpasning til ikke-stationære miljøer ved at lægge større vægt på nylige observationer.

Optimistisk initialisering

I begyndelsen af en træningsproces kan estimaterne for handlingsværdier variere betydeligt, hvilket kan føre til for tidlig udnyttelse. Dette betyder, at agenten kan udnytte sin indledende viden for tidligt og favorisere suboptimale handlinger baseret på begrænset erfaring. For at afbøde dette problem og fremme indledende udforskning er en enkel og effektiv teknik optimistisk initialisering.

Ved optimistisk initialisering initialiseres handlingsværdier til relativt høje værdier (f.eks. Q0(a)=1Q_0(a) = 1 i stedet for 0). Denne tilgang skaber indtrykket af, at alle handlinger er indledningsvist lovende. Som resultat motiveres agenten til at udforske hver handling flere gange, før den vælger det bedste valg. Denne teknik er mest effektiv, når den anvendes sammen med konstant trin-størrelse.

Note
Bemærk

Den optimale handlingsrate i denne og fremtidige grafer refererer til andelen af miljøer, hvor den optimale handling blev valgt på et givent tidspunkt.

For eksempel, hvis der er 10 testmiljøer, og den optimale handling blev valgt i 6 af dem ved tidssteg 200, vil den optimale handlingsrate for dette tidssteg være 0.6. Denne måling er nyttig til at evaluere præstation, fordi den korrelerer med maksimering af belønning uden at afhænge af de præcise belønningsværdier.

question mark

Hvad bruges gennemsnitsestimatet til i estimering af handlingsværdier?

Select the correct answer

Var alt klart?

Hvordan kan vi forbedre det?

Tak for dine kommentarer!

Sektion 2. Kapitel 2
some-alt