Theorem (Value iteration)

Suppose the cost function is non-negative. Consider the successive iteration $$v_{n}(x)=\min_{u}\left\{ c(x,u)+\beta \int\limits _{\mathbb{X}}v_{n-1}(y)\,\mathcal{T}(dy|x,u) \right\},\forall x,n\ge 1$$with $v_{0}(x)=0,\forall x\in\mathbb{X}$. Then, $v_{n}$ is a monotonically non-decreasing sequence. If this sequence converges point wise to a function $v$ where $$v(x)=c(x,f(x))+\beta \int\limits v(y) \, \mathcal{T}(dy|x,f(x))$$is such that with $\gamma=\{ f,f, \dots \}$ then $$\lim_{ n \to \infty } \beta^{n}E_{x}^{\gamma}[v(x_{n})]=0$$which means $\gamma$ is optimal and $v$ is the value function.