Convergence of value iteration

Question

Why is the termination condition of the value-iteration algorithm ( example http://aima-java.googlecode.com/svn/trunk/aima-core/src/main/java/aima/core/probability/mdp/search/ValueIteration.java ) as it is?

In the MDP (Markov Decision Process) we have

$||U_{i+1}-U_i||< \text{error}\cdot(1-\gamma)/\gamma$, where

$U_i$ is a vector of utilities
$U_{i+1}$ is the vector of updated utilities
$\text{error}$ is the error bound used in the algorithm
$\gamma$ is the discount factor used in the algorithm

• Where does "$\text{error}\cdot(1-\gamma)/\gamma$" come from?
• Is the term "$/\gamma$" because every step is discounted by $\gamma$? But then what about $\text{error}\cdot(1-\gamma)$?
• And how big must $\text{error}$ be?

Answer 1

It's due to the basic convergence proof of value iteration. To state the result using your notation,

$||U_{\infty}-U_i|| < \epsilon/2$ whenever $||U_{i+1}-U_i|| < \epsilon(1-\gamma)/2\gamma$ $\hspace{2cm}$ with $\gamma <1$

We are bounding the overall error of the value iteration this way, not just terminating the algorithm when successive iterations differ by less than some value $\delta$- which, without the convergence proof, would not provide an upper bound on the overall error.

Clearly this is more useful than just stopping at some user-specified $||U_{i+1}-U_i||$, where the user has to do the work to convert from the $\delta$ to the bound (or the reverse.)

For the proof itself, see Puterman 161-163.