Proposition 9 — under D, and D.1 or J_N = T^N(J̄) for all N, the DP algorithm converges: J_∞ = J*

In the abstract dynamic programming model of Bertsekas (1977), the dynamic programming algorithm generates $T(\bar J),T^2(\bar J),\dots$, where $T(J)(x)=\inf_{u\in U(x)}H(x,u,J)$, and its limit is

Let $J_N$ be the optimal value function of the $N$-stage problem (36) and $J^*=\inf_{\pi\in\Pi}J_\pi$ the optimal value function. Suppose Assumption D holds, and that either

1. Assumption D.1 holds, or
2. $J_N=T^N(\bar J)$ for all $N=1,2,\dots$.

Then

That is, under uniform decrease the value iteration started from $\bar J$ converges to the optimal value function. Under the uniform increase assumption the analogous statement can fail even for simple deterministic problems.

Formalization Note $J_\infty$ is limUnder atTop of the sequence $T^N(\bar J)(x)$, which is nonincreasing under D and so converges in $[-\infty,\infty]$.