The solution to Bellmann's Equation

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

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

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

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?

Thank you in advance, R.G.

(P.S. I am unsure if the tags "optimization" and "proof-verification" are appropriate for this questions. Please feel free to remove them if this is not the case.)

  • $\begingroup$ 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$. $\endgroup$ – mikkola Nov 21 '16 at 19:17
  • $\begingroup$ 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). $\endgroup$ – R.G. Nov 22 '16 at 12:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.