Contraction Mapping
From the book
Chapter 15: Bellman Equations and Operators. In the chapter mind map this icon labels **Bellman Operators Contraction Mapping. The discussion below is excerpted and lightly edited from § Bellman Operators & Contraction Mapping** in Mathematics for AI and Machine Learning. Related material also appears in Chapter 6 ($A^k$ & $\rho(A)$).
The Bellman operator $T_\pi$ and the Bellman optimality operator $T_*$ are contraction mappings on the space of value functions with the supremum norm:
|T_\pi \mathbf{v}_1(s) - T_\pi \mathbf{v}_2(s)| &= \left|\sum_{a} \pi(a | s) \gamma \sum_{s'} P(s' | s, a) (\mathbf{v}_1(s') - \mathbf{v}_2(s'))\right| \\
&\le \sum_{a} \pi(a | s) \gamma \sum_{s'} P(s' | s, a) |\mathbf{v}_1(s') - \mathbf{v}_2(s')| \\ &\le \gamma \max_{s'} |\mathbf{v}_1(s') - \mathbf{v}_2(s')| = \gamma \|\mathbf{v}_1 - \mathbf{v}_2\|_\infty. \end{aligned} $$
What this drawing shows
What you see. Outer metric domain and inner contracted image fixed; blue iterates shrink toward the red fixed point $V^*$.
In the mind map. Chapter 15 — Bellman Operators Contraction Mapping. See From the book above for definitions, figures, and worked examples.
Also appears in Ch. 6 (&).
Where to read next
Read the full definitions, figures, and worked examples in Chapter 15: Bellman Equations and Operators — see the mind-map node Bellman Operators Contraction Mapping.
This concept is also referenced in Chapter 6 (&).