Policyutvärdering
Policyevaluering är en process för att bestämma värdefunktionen för en given policy.
Policyevaluering kan användas för att uppskatta både tillståndsvärdefunktion och aktionsvärdefunktion. Men för DP-metoder kommer tillståndsvärdefunktionen att användas.
Som du vet kan en tillståndsvärdefunktion för en given policy bestämmas genom att lösa en Bellman-ekvation:
vπ(s)=a∑π(a∣s)s′,r∑p(s′,r∣s,a)(r+γvπ(s′))Om du har en fullständig modell av miljön (dvs. kända övergångssannolikheter och förväntade belöningar för alla tillstånd-handlingspar), är de enda okända variablerna som återstår i ekvationen tillståndsvärdena. Därför kan ekvationen ovan omformuleras som ett system av ∣S∣ linjära ekvationer med ∣S∣ okända.
Till exempel, om en MDP har 2 tillstånd (s1, s2) och 2 handlingar (flytta till s1, flytta till s2), kan tillståndsvärdesfunktionen definieras så här:
{V(s1)=0.5⋅(5+0.9⋅V(s1))+0.5⋅(10+0.9⋅V(s2))V(s2)=0.7⋅(2+0.9⋅V(s1))+0.3⋅(0+0.9⋅V(s2))Detta kan lösas med standardtekniker inom linjär algebra.
En unik lösning för ett sådant linjärt system är garanterad om minst ett av följande villkor är uppfyllt:
- Diskonteringsfaktorn uppfyller γ<1;
- Policyn π, när den följs från ett godtyckligt tillstånd s, säkerställer att episoden så småningom avslutas.
Iterativ policyevaluering
Lösningen kan beräknas direkt, men en iterativ metod används oftare på grund av dess enkla implementering. Denna metod börjar med att tilldela godtyckliga initialvärden till alla tillstånd, förutom terminala tillstånd, vilka sätts till 0. Värdena uppdateras sedan iterativt med hjälp av Bellmans ekvation som uppdateringsregel:
vk+1(s)←a∑π(a∣s)s′,r∑p(s′,r∣s,a)(r+γvk(s′))Den uppskattade tillståndsvärdesfunktionen vk konvergerar slutligen till den sanna tillståndsvärdesfunktionen vπ när k→∞ om vπ existerar.
Strategier för värdebackup
Vid uppdatering av värdeuppskattningar beräknas nya uppskattningar baserat på tidigare värden. Processen att bevara tidigare uppskattningar kallas en backup. Det finns två vanliga strategier för att utföra backups:
- Full backup: denna metod innebär att de nya uppskattningarna lagras i en separat array, skild från den som innehåller de tidigare (backupade) värdena. Följaktligen krävs två arrayer — en för att behålla de tidigare uppskattningarna och en annan för att lagra de nyberäknade värdena;
- In-place backup: denna metod håller alla värden i en enda array. Varje ny uppskattning ersätter omedelbart det tidigare värdet. Denna metod minskar minnesanvändningen, eftersom endast en array behövs.
Vanligtvis föredras metoden in-place backup eftersom den kräver mindre minne och konvergerar snabbare tack vare den omedelbara användningen av de senaste uppskattningarna.
När ska uppdateringen avslutas?
Vid iterativ policyevaluering finns det ingen exakt punkt då algoritmen bör avslutas. Även om konvergens är garanterad i gränsen, är fortsatta beräkningar bortom en viss punkt onödiga i praktiken. Ett enkelt och effektivt stoppkriterium är att övervaka den absoluta skillnaden mellan på varandra följande värdeuppskattningar, ∣vk+1(s)−vk(s)∣, och jämföra den med en liten tröskel θ. Om, efter en fullständig uppdateringscykel (där värden för alla tillstånd uppdateras), inga förändringar överstiger θ, kan processen säkert avslutas.
Pseudokod
Tack för dina kommentarer!
Fråga AI
Fråga AI
Fråga vad du vill eller prova någon av de föreslagna frågorna för att starta vårt samtal
Can you explain the difference between full backup and in-place backup in more detail?
How does the choice of the discount factor γ affect convergence?
Can you walk me through the pseudocode for iterative policy evaluation?
Awesome!
Completion rate improved to 2.7Policyutvärdering
Svep för att visa menyn
Policyevaluering är en process för att bestämma värdefunktionen för en given policy.
Policyevaluering kan användas för att uppskatta både tillståndsvärdefunktion och aktionsvärdefunktion. Men för DP-metoder kommer tillståndsvärdefunktionen att användas.
Som du vet kan en tillståndsvärdefunktion för en given policy bestämmas genom att lösa en Bellman-ekvation:
vπ(s)=a∑π(a∣s)s′,r∑p(s′,r∣s,a)(r+γvπ(s′))Om du har en fullständig modell av miljön (dvs. kända övergångssannolikheter och förväntade belöningar för alla tillstånd-handlingspar), är de enda okända variablerna som återstår i ekvationen tillståndsvärdena. Därför kan ekvationen ovan omformuleras som ett system av ∣S∣ linjära ekvationer med ∣S∣ okända.
Till exempel, om en MDP har 2 tillstånd (s1, s2) och 2 handlingar (flytta till s1, flytta till s2), kan tillståndsvärdesfunktionen definieras så här:
{V(s1)=0.5⋅(5+0.9⋅V(s1))+0.5⋅(10+0.9⋅V(s2))V(s2)=0.7⋅(2+0.9⋅V(s1))+0.3⋅(0+0.9⋅V(s2))Detta kan lösas med standardtekniker inom linjär algebra.
En unik lösning för ett sådant linjärt system är garanterad om minst ett av följande villkor är uppfyllt:
- Diskonteringsfaktorn uppfyller γ<1;
- Policyn π, när den följs från ett godtyckligt tillstånd s, säkerställer att episoden så småningom avslutas.
Iterativ policyevaluering
Lösningen kan beräknas direkt, men en iterativ metod används oftare på grund av dess enkla implementering. Denna metod börjar med att tilldela godtyckliga initialvärden till alla tillstånd, förutom terminala tillstånd, vilka sätts till 0. Värdena uppdateras sedan iterativt med hjälp av Bellmans ekvation som uppdateringsregel:
vk+1(s)←a∑π(a∣s)s′,r∑p(s′,r∣s,a)(r+γvk(s′))Den uppskattade tillståndsvärdesfunktionen vk konvergerar slutligen till den sanna tillståndsvärdesfunktionen vπ när k→∞ om vπ existerar.
Strategier för värdebackup
Vid uppdatering av värdeuppskattningar beräknas nya uppskattningar baserat på tidigare värden. Processen att bevara tidigare uppskattningar kallas en backup. Det finns två vanliga strategier för att utföra backups:
- Full backup: denna metod innebär att de nya uppskattningarna lagras i en separat array, skild från den som innehåller de tidigare (backupade) värdena. Följaktligen krävs två arrayer — en för att behålla de tidigare uppskattningarna och en annan för att lagra de nyberäknade värdena;
- In-place backup: denna metod håller alla värden i en enda array. Varje ny uppskattning ersätter omedelbart det tidigare värdet. Denna metod minskar minnesanvändningen, eftersom endast en array behövs.
Vanligtvis föredras metoden in-place backup eftersom den kräver mindre minne och konvergerar snabbare tack vare den omedelbara användningen av de senaste uppskattningarna.
När ska uppdateringen avslutas?
Vid iterativ policyevaluering finns det ingen exakt punkt då algoritmen bör avslutas. Även om konvergens är garanterad i gränsen, är fortsatta beräkningar bortom en viss punkt onödiga i praktiken. Ett enkelt och effektivt stoppkriterium är att övervaka den absoluta skillnaden mellan på varandra följande värdeuppskattningar, ∣vk+1(s)−vk(s)∣, och jämföra den med en liten tröskel θ. Om, efter en fullständig uppdateringscykel (där värden för alla tillstånd uppdateras), inga förändringar överstiger θ, kan processen säkert avslutas.
Pseudokod
Tack för dina kommentarer!
