벨만 최적방정식의 수렴성

강화학습을 처음 공부하면 마르코프 의사결정 과정에서는 최소한 하나 이상의 최적 정책이 존재한다는 정리를 배우게 된다. 많은 RL 논문에서 이 정리와 비슷한 방식으로 개념을 증명한다. 본 글에서는 왜 하나의 최적 정책이 존재할 수 있는가? 에 대해 정리한 내용이다.

 

필요한 배경지식은 다음과 같다.

 

Background

• Markov Decision Process
• Policy, Return, Bellman Equation
• 거리공간(Metric Spaces)
• 코시수열(Cauchy Sequence)
• 축약사상(Contraction mapping)
• 바나흐고정점정리(Banach Fixed Point Theorem)

 

Markov Decision Process

마르코프 의사결정 과정은 $<S, A, R, P, \gamma>$ 5개의 튜플로 구성된 이산시간 랜덤 프로세스다. 

상태 $ S$: 풀고자 하는 의사결정 문제에서 에이전트가 존재할 수 있는 상태들의 집합

행동 $ A$: 상태에서 에이전트가 취할 수 있는 행동들의 집합

보상 $ R$: 에이전트가 특정 상태에 도달하거나 행동을 취할 때 마다 받는 보상 신호 값

전이확률 $ P$: 특정 상태에서 어떤 행동을 했을 때 다른 상태로 전이할 확률

할인율$ \gamma $: 현재의 보상에 더 가중치를 주기 위한 값

 

Policy, Return, Bellman Equation

정책 $\pi(A_t = a|S_t = s)$: 에이전트가 특정 상태에서 어떤 행동을 취할 확률

리턴 $G_t = \sum_{k=t+1}^T \gamma^{T-k-1}R_{k+1}  $: 누적 보상의 합

가치함수: $V(s) = \mathbb E [G_t|S_t = s]$. 누적 보상합의 기댓값

벨만기대방정식 $V_\pi (s) = \mathbb E_\pi [R_{t+1} + \gamma V(S_{t+1})|S_t = s]$ : 가치함수를 보상과 다음 상태의 가치함수 합의 기댓값으로 재귀적으로 표현한 식. 다이나믹 프로그래밍을 통해 계산 가능

벨만최적방정식 $V^*(s) = \max_{a\in \cal {A}} \mathbb E [R_{t+1} + \gamma V^*(S_{t+1})|S_t = s, A_t=a]$

 

Overview

우리는 다음을 증명하고자 한다.

Theorem: For any finite MDP, there exists an optimal policy π* such that it is better than or equal to every other possible policy π.

 

최적의 정책을 찾으려면 우리는 정책들에 '순서'를 매길 수 있어야 한다. 그런데 정책은 위에서 확률분포라고 했다. 어떻게 정책들에 순서를 매길 수 있을까? 예를 들어 철수의 키가 180이고 영희의 키가 170이라고 하자 철수의 키는 영희보다 크므로 '철수 > 영희' 와 같은 방식으로 순서를 매길 수 있다.

즉, 값들의 크고 작음을 살펴봄으로써 순서를 매길 수 있다. 정책의 경우 정책을 통해 계산되는 가치함수의 값으로 비교를 수행할 수 있다. 두 정책 $\pi_1, \pi_2$의 순서를 매기는 문제는 곧 $V_{\pi_1},V_{\pi_2} $의 대소를 비교하여 나열하는 것과 같다.

 

$$ \pi_1 \ge \pi_2 \ \text{if} \   V_{\pi_1} \ge V_{\pi_2} $$

 

위를 통해 정책의 좋고 나쁨을 비교하는 방법을 알았다. 우리는 어떤 정책이 다른 모든 정책보다  같거나 더 좋다는 것을 보이면 된다. 이에 대한 증명은 바나흐 고정점 정리(Banach Fixed Point Theorem)를 이해해야한다. 바나흐 고정점 정리를 이해하려면 고정점 문제, 거리 공간, 코시 수열, 축약 사상에 대한 지식이 필요하다. 

 

 

고정점문제(Fixed point problem)

고정점 문제는 $f(x) = x$의 해를 구하는 문제이다. 문제의 이름처럼 $x$는 고정점이라고 부른다. 이 문제를 푸는 방법은 매우 간단하다. $x$의 어떤 무작위 시작점을 선택하고 반복적으로 함수값에 넣어서 함수값을 다시 입력으로 사용하면 된다.  함수값이 수렴한다면 해를 찾은 것이 된다. $f^n (x)$를 함수를 $x$에 n번 적용한 함수라고 생각하자. 여기서 $f(x)$는 연속이다.

$$\begin{align} \text{let}, x^* &= \lim_{n \rightarrow \infty} f^n(x_0) \\ f(x^*) &= f(\lim_{n \rightarrow \infty} f^n(x_0)) \\ &= \lim_{n \rightarrow \infty} f(f^n(x_0)) \\ &= \lim_{n \rightarrow \infty} f^{n+1}(x_0)) \\ &= x^* \end{align}$$

함수가 연속이므로 sequential criterion for continuity [4] 에 의해 limit 연산을 밖으로 꺼낼 수 있다. 

 

 

거리공간(Metric space)

거리공간은 거리라는 대수구조가 부여된 집합이다. 집합 내의 두 원소들 사이의 거리를 계산할 수 있다. 

어떤 집합 $X$에 대해서 거리를 다음과 같이 정의한다. 즉 거리는 $X$ 집합 내의 원소들의 순서쌍을 실수로 사상하는 함수다. 

$$ d :X \times X \rightarrow \mathbb R$$

거리 공간은 $(X, d)$와 같이 집합과 거리의 튜플로 표기한다. 거리 공간은 다음과 같은 성질을 지닌다. 

1) $d(x, y) = 0 \leftrightarrow x= y$ (Identify)

2) $d(x, y) \ge 0$ (Non-Negativity)

3) $d(x_a, x_b) = d(x_a, x_b)$ (Symmetry)

4) $d(x_a, x_b) + d(x_b, x_c) \ge d(x_a, x_c)$ (Triangular inequality)

 

 

코시수열(Cachy sequence)

코시 수열은 첨수가 커질수록, 수열이 진행될 수록 두 원소의 값(거리)이 점점 가까워지는 수열이다.

거리 공간 $(X, d)$ 상에서 $X$의 임의의 두 원소 $x_a, x_b$를 선택했을 때, 모든 양수인 $\epsilon > 0$에 대해서 $a, b \ge N \rightarrow d(x_a, x_b) < \epsilon$ 을 만족시키는 정수 $N$이 존재하면 이를 코시수열이라고 한다.

 

 

완비거리공간(Complete Metric space)

임의의 거리 공간 $(X, d)$ 가 주어졌다고 하자, 만약 $X$ 내의 임의의 코시수열이 어떤 값으로 수렴하고 그 값이 $X$에 속한다면, 그 거리공간은 완비성을 갖추었다고 말한다. 간단하게 거리 공간이 꽉 차있다고 생각하면 되겠다. 

 

 

축약사상(Contraction Mapping)

거리공간 상의 두 원소들에 대한 거리 $d(x_1, x_2)$가 있다. 두 원소들을 함수를 통과시켜 다시 거리를 계산한 것을 $d(f(x_1), f(x_2))$라고 하자. 원래의 거리 $d(x_1, x_2)$보다 함수를 통과시킨 원소들의 거리 $d(f(x_1), f(x_2))$가 같거나 작아지면 이를 축약사상이라고 한다. 수식으로는 다음과 같다.

$$ d(f(x_1), f(x_2)) \le \gamma d(x_1, x_2) $$

거리 함수 $d$를 가지는 거리공간 $(X, d)$에서 정의된 어떤 함수 $f$를 정의하자. 임의의 $x, y \in X$에 대하여 $d(f(x), f(y)) \le \gamma d(x, y)$를 만족하는 $\gamma < 1$이 존재하면 $f$를 축약사상이라고 한다.

즉, 축약사상은 두 원소들 사이의 거리를 감소시키게 된다. 

 

 

바나흐 고정점 정리(Banach fixed point theorem)

Theorem: Let $(X, d)$ be a complete metric space and a function $f: X \rightarrow X$ be a contractor then, f has a unique fixed point $x*∈ X (i.e. f(x*)=x*)$ such that the sequence $f(f(f(…f(x))))$ converges to $x*$.

바나흐 고정점 정리는 완비거리공간 상에서 정의된 축약사상이 유일한 고정점을 갖는다는 정리이다. 이를 활용해서 MDP가 최적 정책을 가진다는 것을 보일 수 있다. 고정점 정리를 증명해보자. 

완비거리공간 $(X, d)$ 에서  $X$의 임의의 점 $x_0$ 을 고려해보자. 우리는 이 점으로부터 반복해서 축약사상을 적용하고 수열을 만들어낼 것이다. $X$에 속하는 $n$번째 수열을 사상시켜서 $x_{n+1}$을 얻어낼 수 있다. 이를 0번째까지 반복하면 다음과 같다.

$$x_{n+1} = f(x_n) =  f(f(x_{n-1})) = \cdots =  f^n(x_0), \quad \text {for} \ n \ge 0.$$ $x_{m+1}, x_{n+1}$ 원소들은 m번째, n번째 원소들에 축약사상을 적용한 것이므로 다음과 같다.  $(x_{n+1} = f(x_n))$

$$d(x_{m+1}, x_{n+1}) =  d(f(x_m), f(x_{n}))$$

 

축약사상 $f$를 계속해서 적용해서 수열 $\{x_n \}_{n \in \mathbb N}$을 얻을 수 있었다 여기에 축약사상의 정의를 통해서 다음을 유도할 수 있다.

$$d(x_{m+1}, x_{n+1}) = d(f(x_m), f(x_{n})) \le \gamma d(x_m, x_n)$$

 

 

증명

이제 $x_n$이 코시 수열인지를 보이자. 만약 $ n \ge m \ge 1$이라면 축약사상의 정의와 삼각부등식을 활용해서 다음을 얻게 된다. 

 

$$\begin{align} d(x_n, x_m) &= d(f^n(x_0), f^m(x_0)) \\ &\le \gamma^m d(f^{n-m}x_0, x_0) \\ &\le \gamma^m[d(f^{n-m}x_0, f^{n-m-1}x_0) + d(f^{n-n-1}x_0, f^{n-m-2}x_0) \\ & + \cdots + d(f(x_0), x_0)] \quad (\text{triangle inequality}) \\ &= \gamma^m [d(f^{n-m-1}x_1, f^{n-m-1}x_0) + d(f^{n-m-2}x_1, f^{n-m-2}x_0) \\ & +\cdots + d(x_1, x_0)    \\ &\le \gamma^m \bigg [ \sum_{k=0}^{n-m-1}\gamma^k \bigg ]d(x_1, x_0)  \\ &\le \gamma^m \bigg [ \sum_{k=0}^{\infty}\gamma^k \bigg ]d(x_1, x_0) \\ &\le \bigg( {c^m \over 1-c}\bigg )d(x_1, x_0)\end{align}$$

 

결과적으로 두 원소 사이의 거리는 m이 증가함에 따라 수렴하며, 이는 코시 수열의 정의와 일치한다. $X$가 완비이기 때문에 수열 $(x_n)$도 $X$ 내의 극한값 $x^*$ 로 수렴하게 된다. 극한값 $x^*$ 가 $f$의 고정점이라는 사실은 $f$의 연속성으로부터 유도된다. 

$$ f(x^*) = f (\lim_{n \rightarrow \infty}{x_n}) = \lim_{n \rightarrow \infty}f({x_n}) =  \lim_{n \rightarrow \infty}x_{n+1} = x^*$$

 

 

벨만 최적방정식의 수렴

$B$라는 optimal bellman operator를 정의해보자. 가치함수를 입력 받아서 다시 가치함수를 출력하며, 이는 가치함수를 하나의 벡터로 보았을 때 벡터공간 상에서 벡터를 벡터로 보내는 사상으로 생각할 수 있다. 

$$BV(s) = \max_a R^a_s + \gamma \sum_{s^\prime\in S} P^a_{ss^\prime}V(s^\prime)$$

optimal bellman operator는 재귀적으로 동작하기에 가치함수의 수열을 만들게 된다. 만약 $B$가 어떤 거리 공간 상에서의 축약사상이라면, $B$를 반복적용했을 때 unique한 optimal value function을 얻을 수 있다. (바나흐 고정점정리) 그리고 이것은 최적 정책의 존재성을 유도하게 된다. 따라서 거리공간이 완비이고 $B$가 축약사상이라는 것을 증명하면 된다. 

 

거리공간

가치함수 $V(s)$는 특정 상태를 입력으로 받아 스칼라를 출력한다. 상태의 개수가 유한하다면 모든 상태에 대한 가치함수의 출력값들 $V$는 유한차원 벡터가 된다. 따라서 거리공간은 다음과 같이 정의된다. 지수 부분은 상태공간의 크기를 말한다. (집합의 원소개수)

$$X: V \in \mathbb R^{|\mathbb S|}$$

Finite MDP에서는 보상값이 유한하므로 가치함수의 값은 항상 실수공간에 존재하게 된다. 따라서 거리공간은 완비가 된다.

거리를 정의하기 위해서 L-infinity norm을 사용한다. 이는 다음과 같이 정의되며 X의 집합 중에서 최댓값을 거리로 사용하겠다는 의미이다. 

$$ ||X||_\infty = \max_{i \in [0, |X|]}|X_i|$$ 

위 정의들에 의해 다음의 정리가 유도된다.

Theorem: Bellman operator $B$ is a contraction mapping in the finite space 
$(R, L-infinity)$

증명

가치함수 $V_1, V_2$가 있다고 가정하자

 

1. 첫 번째 둘에서 두 번째 줄로 갈 때 $a^\prime$이 $a$로 대체하게 되는데 이것이 가치함수 값을 감소시켜서 부등식꼴이 된다. 
2. 세 번째 줄에서 네 번째 줄로 갈 때는 거리를 infinity norm을 사용했기에 max에 $s^\prime$이 붙는다.
3. 다섯 번째 줄에서 확률을 다 더한 것은 1이므로 사라지고 축약사상의 꼴을 맞추기 위해 다시 norm을 씌운다. 

결과적으로 벨만 연산자는 축약사상이다. 벨반 연산자를 반복적용하면 바나흐 고정점 정리에 의해 최적의 가치함수로 수렴한다. 그리고 최적 가치함수로부터 최적 정책을 계산할 수 있게 된다!

 

References

[1] https://towardsdatascience.com/why-does-the-optimal-policy-exist-29f30fd51f8c

[2] https://towardsdatascience.com/mathematical-analysis-of-reinforcement-learning-bellman-equation-ac9f0954e19f 

[3] https://stats.stackexchange.com/questions/468361/bellmans-equation-and-existence-of-optimal-policy-for-mdps

[4] https://www.geneseo.edu/~aguilar/public/notes/Real-Analysis-HTML/ch5-continuity.html