# MDP value iteration

In Markov decision processes, what is the guarantee that value iteration chooses the same policy action from a given state for every iteration? I am referring to the slides given by AWM at http://www.autonlab.org/tutorials/mdp09.pdf.

Thanks Udaya

• Has anybody done MDPs? If so, can someone please answer my question? – Udaya Jul 30 '14 at 6:41

Value iteration works by iteratively refining estimates for the value function, given a full model of the MDP. I'm not sure you can really say that the algorithm "chooses" policy actions during this iterative process. Rather, the algorithm loops on every possible state, and for each state $s$, it updates the value $V(s)$ given the existing estimate for the function. You can read the details in Sutton and Barton's reinforcement learning book (see section 4.4).
However, it is true that this update is based on the action $a$ that maximises the value function with the current estimate, i.e.:
$$V(s) = \max_a \sum_s' P^a_{ss'} [R^a_{ss'} + \gamma V(s')]$$ As this maximisation depends on the value function estimates, the 'best' action $a$ might of course change during the iteration process, but will in the end stabilises once the iteration converges to its final estimates for $V(s)$.