Algorithmus - Value-Iteration

• Bewiesen durch:
  • Bellmann-Update
  • Bellmann-Gleichung
• Typen:
  • Epsilon-Greedy ADP
• Konstrukte/Folgerungen:
  • Epsilon-Greedy ADP
• Involvierte Definitionen:
  • MDP
  • Optimale Strategie
  • siehe auch Policy Iteration
• Veranstaltung: EML
• Referenz: @thimm2024 (Abschnitt 4.1.2)

⠀

Algorithmus: Value Iteration

Sei ein Markov-Entscheidungsprozess.
Sei der Diskontierungsfaktor.
Sei die Anzahl der Iterationen.

Als Value Iteration (kurz VI-Algorithmus) zur Berechnung der optimalen Strategie bezeichnen wir folgenden Algorithmus:

---

Eingabe: MDP , Diskontierungsfaktor , Anzahl der Iterationen
Ausgabe: Optimale Strategie für

für alle

repeat
for do

until

for do

return

Anmerkung

und

Häufig wird der VI-Algorithmus auch weiter in die beiden Teil-Algorithmen und aufgespalten, wobei:

---

repeat
for do

until return

Beziehungsweise unter Nutzung einer Strategie

repeat
for do

until return

---

for do

return

---

Damit ergibt sich der VI-Algorithmus auch durch:

für alle

return