Exercise 3.6.2

Value iteration: return bound, convergence, stopping rule, numeric threshold

Reinforcement Learning › Exercises › Lecture 3 · Dynamic Programming › 3.6 Bellman operators and the Banach fixed-point theorem
MediumWritten

You are designing a robot to run a maze. We model this as a discounted, continuing task with discount factor \(\gamma \in [0, 1)\). 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) Let \(K = \{k_1, k_2, \dots\}\) be the set of future timesteps where the robot successfully completes the maze (i.e., receives a reward of +1).

    Write an expression for the return \(G_t\) specifically in terms of the set \(K\). Using this expression, show that the maximum possible return for this robot is bounded from above by \(\frac{1}{1-\gamma}\).

  • (b) For what values of \(\gamma\) is the Value Iteration algorithm guaranteed to converge to the optimal value function \(v_*\)? Does the choice of the initial value function estimate, \(v_0\), matter for this convergence?

  • (c) You decide to use Value Iteration to solve this problem. Since you do not know the true optimal value function \(v_*\), you cannot directly measure the error of your current estimate \(v_k\). However, it is a known property of the Bellman optimality operator that: \[\begin{align*} \parallel v_k - v_* \parallel_{\infty} \leq \frac{\gamma}{1-\gamma} \parallel v_k - v_{k-1} \parallel_{\infty} \end{align*}\] where \(\parallel v_k - v_{k-1} \parallel_{\infty}\) represents the maximum change in the value function between two iterations (a quantity you *can* measure).

    Using the inequality provided above, derive a computable **stopping condition** for the algorithm. That is, find an inequality for \(\parallel v_k - v_{k-1} \parallel_{\infty}\) that guarantees the true error \(\parallel v_k - v_* \parallel_{\infty}\) is less than some user-defined tolerance \(\epsilon\).

  • (d) Suppose you set \(\gamma = 0.99\).

    i. Based on your answer in part (a), what is the maximum possible return the robot can get?

    ii. You want to stop the algorithm only when the error is at most \(1\%\) of that maximum possible return (i.e., \(\epsilon = 0.01 \times \text{MaxReturn}\)). Using your formula from part (c), what is the numerical threshold required for \(\parallel v_k - v_{k-1} \parallel_{\infty}\)?