Value Iteration
From the book
Chapter 15: Bellman Equations and Operators. In the chapter mind map this icon labels Algos: Value & Policy Iteration. The discussion below is excerpted and lightly edited from § Algorithm: Value Iteration in Mathematics for AI and Machine Learning.
``{.algorithm caption="Value Iteration" label="alg:value-iteration"} \Require MDP $(S, A, P, R, \gamma)$, tolerance $\epsilon > 0$ \Ensure Optimal value function $V_$ and optimal policy $\pi_$ \State Initialize $\mathbf{v}_0$ arbitrarily (e.g., $\mathbf{v}_0 = \mathbf{0}$) \State $k \gets 0$ \Repeat \State $\mathbf{v}_{k+1} \gets T_ \mathbf{v}_k$ \Comment{Apply Bellman optimality operator} \State $k \gets k + 1$ \Until{$\|\mathbf{v}_{k+1} - \mathbf{v}_k\|_\infty < \epsilon$} \State Extract optimal policy: $\pi_(s) \gets \arg\max_a [R(s, a) + \gamma \sum_{s'} P(s' | s, a) \mathbf{v}_k(s')]$ for all $s \in S$ \State \Return $\mathbf{v}_k$, $\pi_*$ ``
What this drawing shows
What you see. Bars for $V_k$, $T V_k$, and $V^*$ grow in sequence; arrows appear as value iteration converges.
In the mind map. Chapter 15 — Algos: Value & Policy Iteration. See From the book above for definitions, figures, and worked examples.
Where to read next
Read the full definitions, figures, and worked examples in Chapter 15: Bellman Equations and Operators — see the mind-map node Algos: Value & Policy Iteration.