Exercise 3.6.3
Value iteration: return bound, error bound proof, stopping rule, convergence
You are designing a robot to run a maze. We will model this as a discounted, continuing task. When the robot completes the maze, it receives a reward of +1 and on the next timestep, it deterministically transitions back to the start state to begin again. The robot receives a reward of 0 at all other timesteps.
-
(a) Give an expression for the return \(G_t\) and show that this return is bounded from above by \(\frac{1}{1-\gamma}\).
-
(b) Let \(\mathcal{V}\) denote the set of value functions over the state space. The Bellman optimality operator \(T^{*} : \mathcal{V} \rightarrow \mathcal{V}\) is defined as: \[\begin{align*} (T^{*}v)(s) = \max_a \sum_{s',r} p(s',r|s,a)\big[ r + \gamma v(s') \big] \end{align*}\] The value iteration algorithm uses the update rule \(v_{k+1} \leftarrow T^{*} v_k\). Let \(v_*\) denote the optimal value function, which is the unique fixed point such that \(v_* = T^* v_*\). The operator \(T^*\) is a \(\gamma\)-contraction with respect to the max-norm, meaning \(\parallel T^*v - T^*v' \parallel_{\infty} \leq \gamma \parallel v - v' \parallel_{\infty}\), where \(\parallel v \parallel_{\infty} := \max_s |v(s)|\).
Prove that the error of the value function at iteration \(k\) is bounded by the change in the value function from the previous iteration, according to the following expression: \[\begin{align*} \parallel v_k - v_* \parallel_{\infty} \leq \frac{\gamma}{1-\gamma} \parallel v_k - v_{k-1} \parallel_{\infty} \end{align*}\]
-
(c) Explain the practical importance of the inequality you proved in part (b). How does it allow you to define a concrete stopping condition for the value iteration algorithm, even though you do not know the true optimal value function \(v_*\)?
-
(d) For what values of \(\gamma\) is convergence of value iteration guaranteed? Does the choice of the initial value function, \(v_0\), matter for convergence?