<aside> ✅

Banach Fixed-Point Theorem은 완비 거리 공간에서 수축사상이면 유일한 고정점이 존재하고 반복적용으로 기하급수적으로 수렴한다고 말하는 정리입니다. RL에서 Value Iteration의 수렴성을 이 정리로 증명할 수 있습니다.

</aside>

비공식 설명

• 공간: $(X, d)$가 완비 거리 공간(complete metric space)일 때,

• 연산자: 함수 $f: X \to X$가 **수축사상(contraction mapping)**이면, 즉, 어떤 상수 $0 \leq c < 1$이 존재해서

  $$ d(f(x), f(y)) \leq c \cdot d(x, y), \quad \forall x, y \in X $$

  이 성립한다면,

• 결론:

  1. f에는 유일한 고정점 $x^* \in X$가 존재한다. (i.e., $f(x^) = x^$)
  2. 임의의 시작점 $x_0 \in X$에서 $x_{n+1} = f(x_n)$을 반복하면, $\lim_{n \to \infty} x_n = x^*$으로 수렴한다.
  3. 수렴 속도는 기하급수적(geometric)이다. 즉, $d(x_n, x^*) \leq \frac{c^n}{1-c} d(x_1, x_0)$.

해석

• Kleene 정리는 “단조 + 사슬 상한 존재”라는 순서 구조적 조건 위에서 최소 고정점의 존재와 근사를 보장합니다.
• Banach 정리는 “완비 거리 공간 + 수축성”이라는 위상적 조건 위에서 유일 고정점과 빠른 수렴을 보장합니다.

강화학습과의 연관

• 강화학습에서 Value Iteration은 Bellman 최적 연산자 T^*를 반복 적용하는 알고리즘인데, 이 T^*는 $\|\cdot\|_\infty$-norm에서 $\gamma$-수축사상입니다 (0 < $\gamma$ < 1).
• 따라서 Banach Fixed-Point Theorem을 적용해:
  1. 최적 가치 함수 V^*가 유일하게 존재함을 보장하고,
  2. Value Iteration이 임의의 초기값에서 시작해 V^*로 수렴함을 보장합니다.