Notice: This page requires JavaScript to function properly.
Please enable JavaScript in your browser settings or update your browser.Lära Optimalitetsvillkor | Dynamisk Programmering
Introduktion till Förstärkningsinlärning
course content

Kursinnehåll

Introduktion till Förstärkningsinlärning

Introduktion till Förstärkningsinlärning

1. RL Kärnteori
Vad är RL?RL Jämfört Med Andra InlärningsparadigmMarkovbeslutsprocessEpisoder och BelöningarModell, Policy och VärdenUtforskning kontra ExploateringGymnasium-GrunderUtmaning: Konfigurera en Miljö
2. Multi-Armed Bandit-Problemet
ProbleminledningAktionsvärdenEpsilon-Girig AlgoritmAlgoritm för Övre KonfidensgränsGradientbanditalgoritmUtmaning: Multi-Armed Bandits
3. Dynamisk Programmering
Vad är dynamisk programmering?Bellmans EkvationerOptimalitetsvillkorPolicyutvärderingPolicyförbättringGeneraliserad PolicyiterationPolicyiterationVärdeiterationUtmaning: Dynamisk Programmering
4. Monte Carlo-metoder
Vad är Monte Carlo-metoder?VärdefunktionsuppskattningMonte Carlo-KontrollUtforskningsmetoderOn-Policy Monte Carlo-KontrollOff-Policy Monte Carlo-KontrollInkrementella ImplementationerUtmaning: Monte Carlo-metoder
5. Temporär Differensinlärning
Vad är Temporär Differensinlärning?TD(0): VärdefunktionsuppskattningSARSA: On-Policy TD-InlärningQ-inlärning: Off-Policy TD-inlärningGeneralisering av TD-inlärningUtmaning: Temporär Differensinlärning

book
Optimalitetsvillkor

I föregående kapitel lärde du dig om Bellman-ekvationer för tillståndsvärde- och tillstånd-handlingsvärdefunktioner. Dessa ekvationer beskriver hur tillståndsvärden kan definieras rekursivt genom värdena för andra tillstånd, där värdena är beroende av en given policy. Dock är inte alla policies lika effektiva. Faktum är att värdefunktioner tillhandahåller en partiell ordning för policies, vilket kan beskrivas enligt följande:

π≥π′  ⟺  vπ(s)≥vπ′(s)∀s∈S\pi \ge \pi' \iff v_\pi(s) \ge v_{\pi'}(s) \qquad \forall s \in S

Så policy π\pi är bättre än eller lika med policy π′\pi' om för alla möjliga tillstånd den förväntade avkastningen av policy π\pi inte är mindre än den förväntade avkastningen av policy π′\pi'.

Note
Fördjupning

En partiell ordning följer de vanliga ordningsreglerna men kräver inte att varje par jämförs. I vårt fall kan vi endast rangordna två policies om de ger samma resultat, eller om en tydligt överträffar den andra. I alla andra fall förblir policies ojämförbara.

Optimal policy

Note
Definition

För varje MDP finns det minst en policy som är lika bra som eller bättre än alla andra policies. Denna policy kallas en optimal policy π∗\pi_*. Även om det kan finnas många optimala policies, betecknas alla som π∗\pi_*.

Varför existerar alltid en optimal policy?

Du kanske undrar varför en optimal policy alltid existerar för varje MDP. Det är en bra fråga, och intuitionen bakom detta är förvånansvärt enkel. Kom ihåg att tillstånden i en MDP fångar fullt ut miljöns tillstånd. Detta innebär att varje tillstånd är oberoende av alla andra: åtgärden som väljs i ett tillstånd påverkar inte de belöningar eller utfall som kan uppnås i ett annat. Genom att välja den optimala åtgärden i varje tillstånd separat, når du därför naturligt fram till den övergripande bästa sekvensen av åtgärder genom hela processen. Och denna uppsättning av optimala åtgärder i varje tillstånd utgör en optimal policy.

Dessutom finns det alltid minst en policy som är både optimal och deterministisk. Faktum är att om det för något tillstånd ss finns två åtgärder aa och a′a' som ger samma förväntade avkastning, kommer valet av endast en av dem inte att påverka policyns optimalitet. Om denna princip tillämpas på varje enskilt tillstånd blir policyn deterministisk samtidigt som dess optimalitet bibehålls.

Optimala värdefunktioner

Optimala policys delar samma värdefunktioner — detta blir tydligt när vi betraktar hur policys jämförs. Det innebär att optimala policys delar både tillståndsvärdefunktion och aktionsvärdefunktion.

Dessutom har optimala värdefunktioner sina egna Bellman-ekvationer som kan skrivas utan hänvisning till någon specifik policy. Dessa ekvationer kallas Bellmans optimalitetsekvationer.

Optimal tillståndsvärdefunktion

Note
Definition

Optimal tillståndsvärdefunktion V∗V_* (eller v∗v_*) representerar den maximala förväntade avkastningen som kan uppnås från ett visst tillstånd genom att följa en optimal policy.

Det kan matematiskt definieras så här:

v∗(s)=max⁡πvπ(s)=E⁡π∗[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_*(s) = \max_\pi v_\pi(s) = \E_{\pi_*}[G_t | S_t = s]

Bellmans optimalitetsekvation för denna värdefunktion kan härledas enligt följande:

v∗(s)=∑aπ∗(a∣s)∑s′,rp(s′,r∣s,a)(r+γv∗(s′))=max⁡a∑s′,rp(s′,r∣s,a)(r+γv∗(s′))\begin{aligned} v_*(s) &= \sum_a \pi_*(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr)\\ &= \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr) \end{aligned}

Intuition

Som du redan vet finns det alltid minst en policy som är både optimal och deterministisk. En sådan policy skulle, för varje tillstånd, konsekvent välja en specifik åtgärd som maximerar den förväntade avkastningen. Därför skulle sannolikheten att välja denna optimala åtgärd alltid vara 1, och sannolikheten att välja någon annan åtgärd skulle vara 0. Givet detta behöver den ursprungliga Bellman-ekvationen inte längre summationsoperatorn. Eftersom vi vet att vi alltid kommer att välja den bästa möjliga åtgärden kan vi istället ersätta summan med att ta ett maximum över alla tillgängliga åtgärder.

Optimalt aktionsvärdesfunktion

Note
Definition

Optimalt aktionsvärdesfunktion Q∗Q_* (eller q∗q_*) representerar den maximala förväntade avkastningen som kan uppnås genom att ta en viss handling i ett visst tillstånd och därefter följa den optimala policyn.

Det kan matematiskt definieras som:

q∗(s,a)=max⁡πqπ(s,a)=E⁡π∗[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_*(s, a) = \max_\pi q_\pi(s, a) = \E_{\pi_*}[G_t | S_t = s, A_t = a]

Bellmans optimalitetsekvation för denna värdefunktion kan härledas så här:

q∗(s,a)=∑s′,rp(s′,r∣s,a)(r+γ∑a′π∗(a′∣s′)q∗(s′,a′))=∑s′,rp(s′,r∣s,a)(r+γmax⁡a′q∗(s′,a′))\begin{aligned} q_*(s, a) &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \sum_{a'} \pi_*(a' | s')q_*(s', a')\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \max_{a'} q_*(s', a')\Bigr) \end{aligned}

Intuition

På liknande sätt som för tillståndsvärdefunktionen kan summan ersättas med att ta ett maximum över alla tillgängliga åtgärder.

question mark

Varför existerar alltid en optimal policy för varje Markovbeslutsprocess?

Select the correct answer

Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 3. Kapitel 3

Fråga AI

expand

Fråga AI

ChatGPT

Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal

course content

Kursinnehåll

Introduktion till Förstärkningsinlärning

Introduktion till Förstärkningsinlärning

1. RL Kärnteori
Vad är RL?RL Jämfört Med Andra InlärningsparadigmMarkovbeslutsprocessEpisoder och BelöningarModell, Policy och VärdenUtforskning kontra ExploateringGymnasium-GrunderUtmaning: Konfigurera en Miljö
2. Multi-Armed Bandit-Problemet
ProbleminledningAktionsvärdenEpsilon-Girig AlgoritmAlgoritm för Övre KonfidensgränsGradientbanditalgoritmUtmaning: Multi-Armed Bandits
3. Dynamisk Programmering
Vad är dynamisk programmering?Bellmans EkvationerOptimalitetsvillkorPolicyutvärderingPolicyförbättringGeneraliserad PolicyiterationPolicyiterationVärdeiterationUtmaning: Dynamisk Programmering
4. Monte Carlo-metoder
Vad är Monte Carlo-metoder?VärdefunktionsuppskattningMonte Carlo-KontrollUtforskningsmetoderOn-Policy Monte Carlo-KontrollOff-Policy Monte Carlo-KontrollInkrementella ImplementationerUtmaning: Monte Carlo-metoder
5. Temporär Differensinlärning
Vad är Temporär Differensinlärning?TD(0): VärdefunktionsuppskattningSARSA: On-Policy TD-InlärningQ-inlärning: Off-Policy TD-inlärningGeneralisering av TD-inlärningUtmaning: Temporär Differensinlärning

book
Optimalitetsvillkor

I föregående kapitel lärde du dig om Bellman-ekvationer för tillståndsvärde- och tillstånd-handlingsvärdefunktioner. Dessa ekvationer beskriver hur tillståndsvärden kan definieras rekursivt genom värdena för andra tillstånd, där värdena är beroende av en given policy. Dock är inte alla policies lika effektiva. Faktum är att värdefunktioner tillhandahåller en partiell ordning för policies, vilket kan beskrivas enligt följande:

π≥π′  ⟺  vπ(s)≥vπ′(s)∀s∈S\pi \ge \pi' \iff v_\pi(s) \ge v_{\pi'}(s) \qquad \forall s \in S

Så policy π\pi är bättre än eller lika med policy π′\pi' om för alla möjliga tillstånd den förväntade avkastningen av policy π\pi inte är mindre än den förväntade avkastningen av policy π′\pi'.

Note
Fördjupning

En partiell ordning följer de vanliga ordningsreglerna men kräver inte att varje par jämförs. I vårt fall kan vi endast rangordna två policies om de ger samma resultat, eller om en tydligt överträffar den andra. I alla andra fall förblir policies ojämförbara.

Optimal policy

Note
Definition

För varje MDP finns det minst en policy som är lika bra som eller bättre än alla andra policies. Denna policy kallas en optimal policy π∗\pi_*. Även om det kan finnas många optimala policies, betecknas alla som π∗\pi_*.

Varför existerar alltid en optimal policy?

Du kanske undrar varför en optimal policy alltid existerar för varje MDP. Det är en bra fråga, och intuitionen bakom detta är förvånansvärt enkel. Kom ihåg att tillstånden i en MDP fångar fullt ut miljöns tillstånd. Detta innebär att varje tillstånd är oberoende av alla andra: åtgärden som väljs i ett tillstånd påverkar inte de belöningar eller utfall som kan uppnås i ett annat. Genom att välja den optimala åtgärden i varje tillstånd separat, når du därför naturligt fram till den övergripande bästa sekvensen av åtgärder genom hela processen. Och denna uppsättning av optimala åtgärder i varje tillstånd utgör en optimal policy.

Dessutom finns det alltid minst en policy som är både optimal och deterministisk. Faktum är att om det för något tillstånd ss finns två åtgärder aa och a′a' som ger samma förväntade avkastning, kommer valet av endast en av dem inte att påverka policyns optimalitet. Om denna princip tillämpas på varje enskilt tillstånd blir policyn deterministisk samtidigt som dess optimalitet bibehålls.

Optimala värdefunktioner

Optimala policys delar samma värdefunktioner — detta blir tydligt när vi betraktar hur policys jämförs. Det innebär att optimala policys delar både tillståndsvärdefunktion och aktionsvärdefunktion.

Dessutom har optimala värdefunktioner sina egna Bellman-ekvationer som kan skrivas utan hänvisning till någon specifik policy. Dessa ekvationer kallas Bellmans optimalitetsekvationer.

Optimal tillståndsvärdefunktion

Note
Definition

Optimal tillståndsvärdefunktion V∗V_* (eller v∗v_*) representerar den maximala förväntade avkastningen som kan uppnås från ett visst tillstånd genom att följa en optimal policy.

Det kan matematiskt definieras så här:

v∗(s)=max⁡πvπ(s)=E⁡π∗[Gt∣St=s]\def\E{\operatorname{\mathbb{E}}} v_*(s) = \max_\pi v_\pi(s) = \E_{\pi_*}[G_t | S_t = s]

Bellmans optimalitetsekvation för denna värdefunktion kan härledas enligt följande:

v∗(s)=∑aπ∗(a∣s)∑s′,rp(s′,r∣s,a)(r+γv∗(s′))=max⁡a∑s′,rp(s′,r∣s,a)(r+γv∗(s′))\begin{aligned} v_*(s) &= \sum_a \pi_*(a | s) \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr)\\ &= \max_a \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma v_*(s')\Bigr) \end{aligned}

Intuition

Som du redan vet finns det alltid minst en policy som är både optimal och deterministisk. En sådan policy skulle, för varje tillstånd, konsekvent välja en specifik åtgärd som maximerar den förväntade avkastningen. Därför skulle sannolikheten att välja denna optimala åtgärd alltid vara 1, och sannolikheten att välja någon annan åtgärd skulle vara 0. Givet detta behöver den ursprungliga Bellman-ekvationen inte längre summationsoperatorn. Eftersom vi vet att vi alltid kommer att välja den bästa möjliga åtgärden kan vi istället ersätta summan med att ta ett maximum över alla tillgängliga åtgärder.

Optimalt aktionsvärdesfunktion

Note
Definition

Optimalt aktionsvärdesfunktion Q∗Q_* (eller q∗q_*) representerar den maximala förväntade avkastningen som kan uppnås genom att ta en viss handling i ett visst tillstånd och därefter följa den optimala policyn.

Det kan matematiskt definieras som:

q∗(s,a)=max⁡πqπ(s,a)=E⁡π∗[Gt∣St=s,At=a]\def\E{\operatorname{\mathbb{E}}} q_*(s, a) = \max_\pi q_\pi(s, a) = \E_{\pi_*}[G_t | S_t = s, A_t = a]

Bellmans optimalitetsekvation för denna värdefunktion kan härledas så här:

q∗(s,a)=∑s′,rp(s′,r∣s,a)(r+γ∑a′π∗(a′∣s′)q∗(s′,a′))=∑s′,rp(s′,r∣s,a)(r+γmax⁡a′q∗(s′,a′))\begin{aligned} q_*(s, a) &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \sum_{a'} \pi_*(a' | s')q_*(s', a')\Bigr)\\ &= \sum_{s', r} p(s', r | s, a)\Bigl(r + \gamma \max_{a'} q_*(s', a')\Bigr) \end{aligned}

Intuition

På liknande sätt som för tillståndsvärdefunktionen kan summan ersättas med att ta ett maximum över alla tillgängliga åtgärder.

question mark

Varför existerar alltid en optimal policy för varje Markovbeslutsprocess?

Select the correct answer

Var allt tydligt?

Hur kan vi förbättra det?

Tack för dina kommentarer!

Avsnitt 3. Kapitel 3
some-alt