Exercise 3.6.1
Bellman optimality operator: why γ-contraction gives convergence of value iteration
Consider the value iteration update rule. Instead of an update rule we can also view that equation as an operator \(T^{*}\) that is applied simultaneously to update the value of every state \[v_{k+1} \leftarrow T^{*} v_k.\] That operator is defined as follows: Let \(\mathcal{V}\) denote the set of value functions over some state space, then \(T^{*} : \mathcal{V} \rightarrow \mathcal{V}\), called the Bellman optimality operator is defined as: \[(T^{*}v)(s) = \max_a \sum_{s',r} p(s',r|s,a)\big[ r + \gamma v(s') \big].\] One property of \(T^{*}\) that can be proven (try it) is that it is a \(\gamma\)-contraction with respect to the max-norm \(\parallel . \parallel_{\infty}\). This means that for all value functions \(v,v'\) it holds that \[\parallel T^*v - T^*v' \parallel_{\infty} \leq \gamma \parallel v - v' \parallel_{\infty},\] where \(\parallel v \parallel_{\infty} := \max_s |v(s)|\).
Why is this result important for the convergence of value iteration to a unique \(v_*\)? Assuming the environment contains no terminal states, is this convergence guaranteed for any \(\gamma\)?