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

  • $\begingroup$ Has anybody done MDPs? If so, can someone please answer my question? $\endgroup$ – 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)$.


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.