Contraction Mapping Theorem

$\text{Fixed point}$: $x\in X$ is a fixed point of $f:X\to X$ if

$$f(x)=x$$

$\text{Contraction mapping}$ (or contractive function): $f$ is a contraction mapping if

$$\Vert f(x_1)-f(x_2)\Vert \le \gamma \Vert x_1-x_2\Vert$$

where $\gamma \in (0,1)$, $\Vert \cdot \Vert$is vector norm

翻译成压缩映射

matrix form example:

• $x=f(x)=Ax$, where $x\in {\mathbb{R}}^n,A\in {\mathbb{R}}^{n\times n}$ and $\Vert A\Vert \le \gamma <1$

$$\Vert A{x}_1-A{x}_2\Vert =\Vert A(x_1-x_2)\Vert \le \Vert A\Vert \Vert x_1-x_2\Vert \le \gamma \Vert x_1-x_2\Vert$$

• therefore, $f(x)=Ax$ is a contraction mapping

$\text{Contraction Mapping Theorem}$

For any equation that has the form $x=f(x)$, if $f$ is a contraction mapping, then

• Existence: There exists a fixed point $x^{\ast }$ satisfying $f(x^{\ast })=x^{\ast }$.
• Uniqueness: The fixed point $x$ is unique.
• Algorithm: Consider the iterative process: $x_{k+1}=f(x_k)$ where $k=0,1,2,\dots$. Then, $x_k\to x^{\ast }$ as $k\to \infty$, the convergence rate is exponentially fast.

具体的证明可以看Book-Mathematical-Foundation-of-Reinforcement-Learning Box 3.1