[Remark] Why contraction property is important for Bellman operator

---

---

[Remark] Why contraction property is important for Bellman operator

 

Bellman Equation은 value function이 만족하는 방정식으로 주어진 policy에 대해서 $V_\pi(s)$값에 대한 관계를 나타냅니다. 주어진 policy $\pi$에 대해서 Bellman operator $\mathcal{T}_\pi$와 Bellman optimal operator $\mathcal{T}_*$은 다음과 같습니다. 

$$\mathcal{T}_\pi v = R_\pi + \gamma P_\pi v ~~~~~ (1)$$

$$(\mathcal{T}_\pi v)(s) = \max_{a\in \mathcal{A}} R_s^a  + \gamma \sum_{s' \in \mathcal{S}} v(s') ~~~~~ (2)$$

(1) 식은 주어진 policy 에 대한 Bellman equation을 나타내고, (2)은 최적의 policy에 대한 Bellman optimal equation을 나타냅니다. constraction property는 두 가지 경우 모두에 대해서, 어떤 시작 $v_0$에 상관없이 value iteration이 고정된 $v_*$에 수렴함을 보장해줍니다. 

---

 $\gamma$ - constraction  

The oepator $F$ is a $\gamma$-constraction.

$$ || FX- FY|| \le \gamma ||X-Y||$$

---

 Theorem 1 

The sequence $$X, FX, F^2X, \cdots $$

converges for every $X$. 

---

 Theorem 2 

$F$ has a unique fixed point $X^*$ which satisfies $FX^* = X^*$ and all sequences $X, FX, \cdots $ converges to the unuque fixed point $X^*$ 

---

Theorem 1은 operator를 계속 연산할 경우, 어떤 점으로 수렴됨을 보장합니다. Bellman equation 에서는, Value Function이 해당 점입니다. Value Function을 벡터 형식으로 바꾸면 다음과 같이 바꿀 수 있습니다. 

$$v = \begin{bmatrix} v(s_1) \\ \vdots \\ v(s_n) \end{bmatrix}$$ 

따라서, Thorem 1은 Bellman operator를 vector 상태인 value function에 계속 적용할 경우, 수렴한다는 말입니다. 

 

Theorem 2는 operator 마다 유일한 value function이 있어서, 초기값에 상관없이 항상 해당 value function으로 수렴하는 것을 나타냅니다. 이게 가능한 이유가 contraction 성질 때문이며 해당 고정점으로 점점 수렴해 나가게 됩니다. 실제로 코드로 구현해보겠습니다. 

 

---

1. 파이썬으로 operator를 정의하면 다음과 같습니다. 

 

---

2. 실험 환경은 3개의 state가 있으며, 각 state에서  1, 2, 9 에 해당하는 보상을 얻게 됩니다.  Transition matrix는 하나의 state에서 다음 state로 넘어가는 확률을 나타냅니다.

 

---

3. 이제 4가지 초기 $v(s)$ 를 아무렇게나 설정하고 bellman - operator 연산을 반복적으로 수행하게 됩니다. 

---

[결론] 해당 코드는 반복적으로 value function 값을 업데이트 하는 방식입니다. 실제 코드에서는 결과를 그래프로 표현하기 위해서 저장하는 코드도 함게 들어있습니다. 결과를 보면, 각 state의 value function 값, $v(s)$에 대해서 초기값에 상관없이 동일한 곳으로 수렴하는 것을 확인할 수 있습니다. 수렴한 점을 보면, state에 따라서 $v(s)$값이 다른 것도 알 수 있습니다.

 

초기값에 따른 value iteartion 결과, 동일한 policy에 대해서 모두 같은 값으로 수렴한다. 

 

따라서, 주어진 policy에 대해서 Bellman operator를 통해서, 고정된 value function이 존재하게 됩니다. 강화학습의 목표는 reward를 최대화하는 policy를 찾는 것이기에, 보상을 최대화로 하는 policy에 대해서 value function을 찾을 수도 있습니다. 이 경우는 (2) 식의 Bellman. optimal operator를 사용하는 경우와 같습니다.