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?
  • 1
    $\begingroup$ Your question is unclear. Please explain what you're discussing, expand abbreviations on first use, and otherwise make it as obvious as you can to use what is going on. Are you talking about a Markov decision process? $\endgroup$ – Glen_b Nov 11 '13 at 1:28
  • $\begingroup$ Question is edited $\endgroup$ – user34618 Nov 11 '13 at 11:59
  • $\begingroup$ I have edited as best I can. Please check that I haven't changed your meaning, and edit to fix as necessary. $\endgroup$ – Glen_b Nov 11 '13 at 13:43
  • $\begingroup$ thx for editing $\endgroup$ – user34618 Nov 11 '13 at 14:27

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.

  • $\begingroup$ Thanks for the answer. What about the error value? How big must it be? $\endgroup$ – user34618 Nov 11 '13 at 16:22
  • $\begingroup$ I assume you mean $\epsilon$. That's really up to you. A disadvantage of value iteration w.r.t. policy iteration is that when using the latter, if you get two consecutive iterations with the same policy, you've converged to the optimum policy. With value iteration, however, you can't be sure (w/o a lot of extra work, and often not even then) that even the tiniest error in the final $U_i$ wouldn't be enough to push you into a different policy choice. Nonetheless, if you want a solution that's guaranteed within $\epsilon$ of optimum, use that value in the program. $\endgroup$ – jbowman Nov 11 '13 at 16:30
  • $\begingroup$ the explanation is understandable, but the proof is still unclear, and as I understand this termination condition comes from the proof. $\endgroup$ – user34618 Nov 11 '13 at 23:56
  • $\begingroup$ ||Vγ(dE)infinity−V(n+1)||<=(γ/1-γ)*||V(n+1)-Vn|| where does dE comes from? Puterman says it is some argmax function and how in proof it can be equal to Vγ(dE)infinity==L(Vγ(dE)infinity), as I understand L is bellman update $\endgroup$ – user34618 Nov 12 '13 at 0:08
  • $\begingroup$ The idea is that you only use the value functions which correspond to the best policy (given the previous iteration's result). The dE part is the arg max V(policy), i.e., the best policy. The point is that it's not just a bound on the error of the current estimate of the value function given the current policy, it's a bound on the overall suboptimality of the current policy relative to the long run discounted value of the best policy. $\endgroup$ – jbowman Nov 12 '13 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.