# Why does value iteration converge to the optimal value function in **finite** amount of steps?

Recall reinforcement learning at (specially for notation):

http://cs229.stanford.edu/notes/cs229-notes12.pdf

Assume that we have a finite MDP. Why is it that value iteration converges to the optimal value function in a finite amount of steps? Can we express this runtime asymptotically precisely in terms of variable (maybe the number of states etc)?

Let me share with you my thoughts:

But first Recall value iteration:

and recall Bellman equations:

If we accept that Bellman's equations are in fact optimal, then its obvious why value iteration gets to the optimal value function once it converges (if it converges). Once it converges then:

$$V^*(s) = R(s) + \underset{a \in A}{max} \sum_{s' \in S} P_{sa}(s')V^*(s')$$

should be true so we are done! However, its not entirely clear if it gets to that, i.e. if the update rule does that (even in an infinite number of steps).

I was hoping that the following would be true (but I am not sure):

The update rule only ever increases $V(s)$.

If that is true, then its clear that eventually it would reach the maximum $V(s)$. However, its not clear that even if that were true, that it would do it in a finite amount of steps or even an infinite. It would be nice to see a proof of this, anyone has one?

Every time I try it I get stuck with that question, does the update rule actually help?

Intuitively, it is trying to force Bellman's equation to be true, but, does it actually make it true eventually? how long does it take? Whats the run time?

Also, the update can be implemented in different ways, so choose whatever way you want. To know what I mean by that read the following:

• you should check out Sutton and Barto (free online, particularly the VI section), this is related to the policy improvement theorem. In value iteration, if every value is updated greedily, by the policy improvement theorem the policy is either strictly better, or, the value function doesn't change (which guarantees the value function for the optimal policy). The VI update is across the entire state space, so the value of every state is updated. I'm not aware of convergence rate analysis (likely exists), but it would probably be related to how 'difficult' the environment (Txn dynamics) are
– eqzx
Commented Jan 23, 2017 at 23:16
• the link is dead as of 11/13/23. Commented Nov 13, 2023 at 19:20

An example: $$S = \{s\}, A = \{a\}, R = \frac{1}{2}$$. By taking the only action $$a$$, the next state should be $$s$$ again.
Let's assume initial $$V(s): = 0$$. Updating by bellman formula: $$V(s)= \frac{1}{2}, \frac{3}{4}, \frac{7}{8}...$$