fix_point_proof

Proof of the fixed point equation

Assume you have $v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$, prove the iterative form is apporx to the fix point $v_{\pi }$:

$$v_{k+1}=r_{\pi }+\gamma P_{\pi }{v}_k$$

---

Define the error:

$$\begin{array}{rl}{\delta }_k& =v_k-v_{\pi }\\ \Rightarrow v_k& ={\delta }_k+v_{\pi }\end{array}$$

Such that:

$$\begin{array}{rl}{v}_{k+1}& =r_{\pi }+\gamma P_{\pi }{v}_k\\ \Rightarrow {\delta }_{k+1}+v_{\pi }& =r_{\pi }+\gamma P_{\pi }({\delta }_k+v_{\pi })\end{array}$$

Because we have $v_{\pi }=r_{\pi }+\gamma P_{\pi }{v}_{\pi }$, and we know that $\gamma <1,[P_{\pi }{]}_{ij}<1$

$$\begin{array}{rl}{\delta }_{k+1}& =\gamma P_{\pi }{\delta }_k\\ \Rightarrow \underset{k\to \infty }{\lim }{\delta }_k& ={\gamma }^k{P}_{\pi }^k{\delta }_0=0\end{array}$$

Hence we have:

$$\underset{k\to \infty }{\lim }{v}_k=\underset{k\to \infty }{\lim }({\delta }_k+v_{\pi })=v_{\pi }$$