# Value Iteration in Dynamic Programming: Convergence of Policy?

The solution to Bellmann's Equation

$$J^*(x) = \min_u \mathbb{E}[g(x, u) + J^*(f(x, u))] \tag{1}$$

where $u$ denotes the action (at state $x$), $g$ is the cost function and $f$ is the (probabilistic) state transition can be found by value iteration whereby for any initial estimate $J^{(0)}(x)$ the iteration procedure

$$J^{(k + 1)}(x) = \min_u \mathbb{E}[g(x, u) + J^{(k)}(f(x, u))] \tag{2}$$

converges to the optimal cost $J^*(x)$. I am interested in proving that "convergence" also applies to the policy $u$; more precisely I want to show that assuming (2) has a unique minimizer $u$ for all $J^{(k)}(x)$ there exists an $N$ for every initial condition $J^{(0)}(x)$ such that for all $n \geq N$ $u$ does not change and is equal to $u$ in (1).

Intuitively I would like to proceed by reductio ad absurdum; If the policy $u$ never remains constant, (2) will not converge. If for instance we consider an $\epsilon$ such that for all $n \geq N: \max_x \lvert J^{(n)}(x) - J^*(x) \rvert \leq \epsilon$ I would like to show that using a policy different to that solving (1) at iteration $n \geq N$ implies $\max_x \lvert J^{(n)}(x) - J^*(x) \rvert > \epsilon$. So far, however, this approach has not been very fruitful.

Does my approach appear reasonable or do you have any other suggestions (or possibly even solutions) to share?

• What is it in your problem or constraints that makes you believe an optimal policy is unique? Although the value function converges to a fixed point, it does not imply the same for an optimal policy. A simple counterexample is a problem where for some $u_1 \neq u_2$, $g(x,u_1) = g(x,u_2) \forall x$. – mikkola Nov 21 '16 at 19:17
• This is precisely an assumption made to prevent the kind of counterexamples you proposed; alternatively, another way to phrase the question might be to say that for $n \geq N$ we require $u$ to be equal to any solution of (1). – R.G. Nov 22 '16 at 12:52