[ ]

Banach Fixed-point Theorem

The Banach fixed-point theorem (a.k.a. the contraction mapping theorem or contraction mapping principle) is an important tool in the theory of metric space; it guarantees the existence and uniqueness of fixed-points of certain self-maps of metric spaces, and provides a constructive method to find those fixed-points.

1. Statement

Definition (Contraction Mapping) Let $(X,d)$ be a metric space. Then a map $T:X\mapsto X$ is called a contraction mapping on $X$ if there exists $q\in [0,)1$ such that $d(T(x),T(y))\le qd(x,y)$ for all $x,y\in X$.

Theorem (Banach Fixed-point Theorem) Let $(X,d)$ be a non-empty complete metric space with a contraction mapping $T:X\mapsto X$. Then $T$ admits a unique fixed-point $x^\ast$ in $X$ (i.e. $T(x^\ast)=x^\ast$).

Furthermore, $x^\ast$ can be found as follows: start with an arbitrary element $x_0$ in $X$ and define a sequence ${x_n}$ by $x_n=T(x_{n-1})$, then $x_n\to x^\ast$.

2. Proof

Let $x_0\in X$ be arbitrary and define a sequence ${x_n}$ by setting $x_n=T(x_{n-1})$. We first note that for all $n\in \mathbb{N}$, we have $d(x_{n+1},x_n)\le q^nd(x_1,x_0)\tag{2.1}$ given that $T$ is a contraction mapping. Then we can show that ${x_n}$ is a Cauchy sequence. Without loss of generality, let $m,n\in\mathbb{N}$ such that $m>n$. % Then for $\forall\varepsilon>0$, we can find a large $N\in\mathbb{N}$ $N=\lceil\log_q\frac{\varepsilon(1-q)}{d(x_1,x_0)}\rceil$ and let $m,n>N$ we have $% $ This proves that ${x_n}$ is a Cauchy sequence. By completeness of $(X,d)$, the sequence has a limit $x^\ast\in X$. Furthermore, the $x^\ast$ must be a fixed-point of $T$: $x^\ast=\lim_{n\to\infty}x_n=\lim_{n\to\infty}T(x_{n-1})=T(\lim_{n\to\infty}x_{n-1})=T(x^\ast)$ (As a contraction mapping, $T$ is continuous, so bringing the limit inside $T$ was justified.)

Lastly, $T$ cannot have more than one fixed point in $(X,d)$, since any pair of distinct fixed points $p_1$ and $p_2$ would contradict the contraction of $T$: $d(T(p_1),T(p_2))=d(p_1,p_2)>qd(p_1,p_2)$

3. Applications

It can be used to prove existence and uniqueness of solutions to value iteration, policy iteration, and policy evaluation of reinforcement learning.

Appendix

Metric space

A metric space is a tuple $(M,d)$ where $M$ is a set and $d$ is a metric on $M$, i.e., a function $d:M\times M\mapsto\mathbb{R}$ such that for any $x, y, z \in M$, the following holds:

Axioms Names
$d(x,y)=0\Leftrightarrow x=y$ identity of indiscernibles
$d(x,y)=d(y,x)$ symmetry
$d(x,y)\le d(x,z)+d(y,z)$ triangle inequality

Using the above three properties, we can easily induce the forth axiom:

Axioms Names
$d(x,y)\ge 0$ non-negativity

Cauchy completion

A metric space $(M,d)$ is called complete (or a Cauchy space) if every Cauchy sequence of points in $M$ has a limit that is also in $M$.

Cauchy sequence

Given a metric space $(M,d)$, a sequence $x_1,x_2,\dots$ is Cauchy, if for every possible positive real number $\varepsilon>0$ there exists a positive integer $N$ such that for all positive integer $m,n>N$, the distance $d(x_m,x_n)<\varepsilon​$.