5
$\begingroup$

I am a little bit confused regarding the value iteration algorithm. When I loop over states should I visit the terminal states, if any, or not?

In Sutton's book on page 83 it says that we do not need to visit the terminal states (loop over each state S, not S+) but every other reference does not make distinction between terminal and not terminal states.

Sutton's book: https://drive.google.com/file/d/1opPSz5AZ_kVa1uWOdOiveNiBFiEOHjkG/view

Improve this question
$\endgroup$
6
$\begingroup$

The point of visiting a state in value iteration is in order to update its value, using the update:

$$v(s) \leftarrow \text{max}_a[\sum_{r,s'} p(s', r|s,a)(r + \gamma v(s'))]$$

First thing to note is that the state value of terminal state $s^T$ is $v(s^T) = 0$, always, since by definition there are no future rewards to accumulate. It definitely would not be a valid calculation that found a possible reward or different next state after a terminal state and updated the value to be non-zero.

You can define things so that it is valid to run the update. If you implement terminal states as "absorbing states" then this means $p(s^T, 0|s^T,*)=1$, and probability of any other state, reward pair is zero, so running the update as above results in updating $0$ to $0$.

In general there is no point updating the value function of a terminal state, although with correct definitions of transition and reward functions there is no harm to do so, it is just wasted calculations.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for your answer. If I choose to formulate the MDP with absorbing states rather than terminal states should I choose a discount smaller than 1 in order for the algorithm to converge or the convergence depends also on the rewards? $\endgroup$ – gnikol Oct 14 '18 at 8:01
  • $\begingroup$ Will the value iteration always converge if I have terminal states in the MDP even if I use a discount 1? $\endgroup$ – gnikol Oct 14 '18 at 8:06
  • 1
    $\begingroup$ @gnikol: Yes it will always converge in the tabular version. Including absorbing states will make no real difference to that, since they contribute values of $0$, and remain stable at $0$ no matter how you iterate. High discount rates might combine with other factors (long episodes and/or loops) to make convergence take longer, but that is not really affected by how you handle the terminal states. $\endgroup$ – Neil Slater Oct 14 '18 at 8:27

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.