David Silver의 Reinforcement Learning 3강에서는 $q_\pi(s,a)$를 이용해 수렴성을 보이는데, 좀 의문이 들어서 fixed-point iteration, 바나흐 고정점 정리에 기반해 Iterative Policy Evaluation의 수렴성을 따로 증명해 보려고 한다.

강의에서 소개한 대로, 단순히 $v_{\pi '}(s) \ge v_\pi(s)$을 보이는 것만으로는 수렴성을 증명할 수 없다고 본다. 첫째로, 등호가 들 어가면 improvement가 일어난다고 보장할 수 없고, 둘째로 improvement가 stop한다고 보장할 수 없기 때문이다. if improvement stop 이라고 강의노트에 써있는데 그 if가 일어나는지 아닌지를 보여야 하는 거 아닌가? 라고 생각을 했는데 강의노트 맨 끝자락을 보니 contraction mapping theorem이 이미 적혀있다! 역시..

일단 쓴 글을 지우기는 아까우니 글은 계속 남겨둔다.

먼저 fixed-point iteration에 대해 알아보자.

Fixed point iteration

이는 $x=f(x)$인 $x$를 찾는 것, 다시 말해 fixed point를 찾는 것과 같다.
그리고 fixed point를 찾는 방법으로는 fixed point iteration이 널리 알려져 있다.
$$x_{k+1} = f(x_k)$$
이 과정을 반복하면 찾고자 하는 fixed point가 찾아진다는 것이다.

하지만 당연히 이는 제약 조건이 존재한다. $f$가 contraction mapping이어야 한다는 것인데, 다시 말해 $f$의 Lipschitz constant $L$이 $L<1$을 만족해야만 한다. 바나흐 고정점 정리(Banach Fixed Point Theorem)이라는 이름으로 축소 사상에 대해 고정점이 '유일'하게 '존재'한다는 것이 알려져 있다. 그리고 바나흐 고정점 정리에서 존재성을 보일 때 사용하는 방법이 fixed point iteration과 동일하므로, 사실상 바나흐 고정점 정리가 그 자체로 fixed point iteration의 유효성을 증명해 주는 셈이다. 궁금한 사람은 https://freshrimpsushi.github.io/posts/proof-of-banach-fixed-point-theorem/ 를 읽어보자.

영문 위키백과에서는 수식 전개를 통해 $|x_n-x_{n-1}|\le L^{n-1}|x_1-x_0|$을 보이고 있다. https://en.wikipedia.org/wiki/Fixed-point_iteration#Contractions을 참고하자. 이는 $x_{n+1}=f(x)$를 통해 생성한 수열의 인접한 두 항 사이 거리가 0으로 수축(contraction)한다는 뜻이다. 살짝 다른 관점으로는 야코비안으로도 설명이 가능할 듯하지만 그냥 시야를 넓혀주는 정도 의미가 있을듯..

Iterative Policy Evaluation의 수렴성 증명

value function은 Bellman Expectation Equation에 의해 아래 관게를 따른다.
$$v^{k+1}=R^\pi+\gamma P^\pi v^k$$

그리고 $f(v)=R^\pi+\gamma P^\pi v$로 두면, $J=|\dfrac{df}{dv}|=\gamma |P^\pi|$이다. 그리고 마르코프 transition matrix $P$의 고윳값은 적어도 하나가 1이고, 나머지는 전부 $|\lambda|<1$을 만족한다. 특히 $P$가 모든 성분이 양수인 regular transition matrix 라면 $\lambda=1$의 대수적 중복도가 1로, $|P|<1$이다.^[1] 그렇지 않더라도 $|P|=1$일 텐데, $\gamma<1$이라면 $J=\gamma|P^\pi|<1$으로, $f$는 contraction mapping이 된다. 따라서 Banache Fixed Point Theorem에 의해 Iterative Policy Evaluation 후 $v$는 Bellman Expectation Equation을 만족하도록 수렴한다.

물론, $f(v)$는 iteration에 따라 $P^\pi$가 변해야 한다는 맹점이 있다. 하지만 이를 고려해도 $|v_{n+1}-v_{n}|$이 0으로 수렴함을 보일 수 있기에 괜찮다. 립시츠 상수가 아무리 커도 $\gamma$이기 때문이다.