Summary  
Value iteration is a dynamic programming method that repeatedly applies the Bellman optimality update to merge policy evaluation and policy improvement into a single step, directly converging to the optimal value function from which the optimal policy is derived.

General domain of usage  
Reinforcement learning

Selv om **policy iteration** er en effektiv metode for å løse **MDP-er**, har den en betydelig ulempe: hver iterasjon innebærer et eget trinn for **policy evaluation**. Når **policy evaluation** utføres **iterativt**, krever det flere gjennomganger av hele **state space**, noe som fører til betydelig beregningsmessig belastning og lengre kjøretider.

Et godt alternativ er **value iteration**, en metode som kombinerer policy evaluation og policy improvement i **ett enkelt trinn**. Denne metoden oppdaterer verdifunksjonen direkte til den konvergerer mot **optimal value function**. Når konvergens er oppnådd, kan **optimal policy** utledes direkte fra denne optimale verdifunksjonen.

**Value iteration** fungerer ved å utføre kun én backup under policy evaluation før policy improvement. Dette gir følgende oppdateringsformel:

$$
v_{k+1}(s) \gets \max_a \sum_{s',r}p(s',r|s,a)\Bigl(r+\gamma v_k(s')\Bigr) \qquad \forall s \in S
$$

Ved å gjøre Bellmans optimalitetslikning om til en oppdateringsregel, slås policy evaluation og policy improvement sammen til ett trinn.

Basert på pseudokoden, når stopper verdiiterasjonen?

Reinforcement Learning (RL) er en kraftig gren av maskinlæring som fokuserer på å trene intelligente agenter gjennom interaksjon med sitt miljø. I dette kurset lærer du hvordan agenter gradvis oppdager effektive atferder gjennom prøving og feiling. Du starter med grunnleggende konsepter som Markov beslutningsprosesser og multi-armede banditter, og fortsetter med dynamisk programmering, Monte Carlo-metoder og temporal difference-læring.

Lær hvordan man trener agenter til å ta optimale beslutninger gjennom prøving og feiling. Utforsk det grunnleggende innenfor teori om forsterkende læring. Få praktisk erfaring med å sette opp og kjøre et Gymnasium-miljø.

Forstå utforskning-utnyttelse-avveiningen gjennom multi-armet bandittproblem. Implementering av handlingsverdiestimering, ε-grådig, øvre konfidensgrense og gradient-bandittmetoder. Evaluering av algoritmers ytelse på simulerte belønningsmaksimeringsoppgaver.

Behersk dynamisk programmering for modellbasert RL. Oppdag hvordan Bellman-likninger kan brukes til å evaluere og forbedre policyer. Implementering av policy- og verdiiterasjonsalgoritmer. Utforsk generalisert policyiterasjon som det teoretiske grunnlaget for modellfrie metoder.

Behersk Monte Carlo-metoder for modellfri RL. Estimer verdifunksjoner og utled optimale policyer fra fullstendige episoder. Implementer on-policy og off-policy Monte Carlo-kontrollalgoritmer. Utforsk strategier for utforskning for å optimalisere modellfri læring.

Behersk temporal difference-læring for modellfri RL. Estimeringsmetoder for verdifunksjoner fra delvise episoder ved bruk av TD(0)-oppdateringer. Implementering av on-policy SARSA og off-policy Q-Learning-algoritmer. Utforsk hvordan Monte Carlo-metoder og TD-læring kombineres i n-trinns TD og TD(λ).

Verdiiterasjon

Hvordan fungerer det?

Pseudokode