[Ch.3] Bellman Equation

이번 포스팅에서는 Ch.2의 연장선으로 MDP로 정의된 문제를 풀 때 등장하는 2가지 value function들의 관계에 대해 다루겠습니다. Ch.2의 state value function과 action value function들의 관계로 현재 state/action과 다음 state/action과의 관계식이 만들어지는데 이를 Bellman Equation이라고 합니다. 강화학습은 이런 Bellman Eqn.을 푸는 과정이라고 볼 수 있습니다.

 

---

Bellman Expectation Equation

 Bellman Eqn.은 Expectation과 Optimality, 두 가지 종류가 있는데 먼저 Expectation Eqn.부터 살펴보겠습니다. MDP에서의 두 가지 value func에 따라 각각 Bellman Equation이 형성됩니다. 

 

 State-value function

 MDP의 State-value function은 정의대로 아래와 같습니다.

그리고 

 의 관계식에 따라 다음과 같이 decomposed 됩니다. 

 

<Fig1. State-value function>

 

여기서 ①은 t+1 시점에 받는 reward, 즉, immediate reward이며 ②는 future reward의 discounted factor가 곱해진 것입니다. 주목해야할 것은 현재 시점(t)의 state-value func.이 바로 다음 시점(t+1)의 state-value func.로 표현된다는 것입니다.

 

하지만 위 식으로는 실제로 구현하는 것이 힘듭니다. 따라서, 직접 구현하기 위해서는 조금 더 tangible한 form으로의 변형이 필요합니다. 이는 위 관계식을 MDP 상에서 각 요소들의 관계에 대해 생각해보면 가능합니다. 

 

<Fig2. State-value function(2)>

 

 현재 시점(t) state에서 가능한 action들이 a1, a2, a3 세 가지가 있다고 가정해봅시다. 그러면 agent가 선택한 당시의 policy에 따라 action을 할 확률이 정해지고, 그 때의 action-value function을 얻을 수 있습니다. 그러면 우리는 state-value function의 Expectation을 각 action을 할 확률(policy)와 그 action의 value function을 곱한 것의 합으로 표현할 수 있게 됩니다. 이런 형태라면 우리는 Expectation을 computable한 형태로 표현하였다고 할 수 있습니다. 

 

하지만, 이 형태로는 next state-value func.과의 관계가 눈에 들어오지 않습니다. 따라서 q-func.(action value funct.)에 대해서 조금 더 식을 전개해보겠습니다. 아래와 같이 action-value func.이 표현될 수 있습니다.

   

<Fig3. Action-value function>

 

 State s에서 action a를 했을 때의 그 action에 대한 value는 두 가지의 요소로 구성되어 있습니다. state s에서 action a를 했을 때의 reward와 그 다음 state의 value func.입니다. 그런데 이 중 이 다음 state-value func. Vπ(s')는 t+1 시점에서의 value func. 이므로 discount factor를 적용해줘야합니다. 또한, deterministic한 env.이 아니라면, 현재(t) state s에서 다음(t+1) state s'으로 전이될 확률도 적용시켜줘야합니다. 그래서 위와 같은 식이 도출됩니다. 이제 Fig.2의 q-func.을 Fig.3의 form으로 넣어 하나로 정리하면 다음과 같습니다.

 

 

이제 이 식으로 보면 Vπ(s')와 Vπ(s)의 관계가 눈에 들어오네요.

 Action-value function

 마찬가지로  Fig.3의 Vπ(s')을 Fig.2의 form으로 바꾸어 정리하면 다음 식을 얻을 수 있습니다.

 

 

이렇게 우리는 state, action-value func.의 Bellman Expectation Equation을 computable한 form으로 변형하고, 다시 현재와 바로 다음 state/action 간의 관계가 드러나도록 정리를 하여 아래와 같은 식을 얻었습니다. 

 

 

 
 여기서 잠시 Bellman Eqn.가 어떤 것인지 조금 위에서 바라보기 위해 강화학습의 과정을 다시한번 되짚어보겠습니다. 

1. 처음 agent가 경험하는 state s나 action에 대한 값들은 모두 의미없는 값들입니다(0 혹은 random number). 
2. 그리고 최적의 policy도 모른 상태로 random요소를 가미하여 이것저것 action을 선택해봅니다. 
3. 그런 과정에서 env.과 상호작용을 하면서 얻은 reward와 state에 대한 정보들을 통해서 어떤 state에서 어떤 action을 하는 것이 좋은지(최대의 reward를 얻을 수 있는지)를 판단합니다.
4. 이때 이를 판단하는 수단이 state-value func.과 action-value func.이고, 이것을 Bellman eqn.을 가지고 update하며 점점 높은 reward를 얻을 수 있는 state를 찾아가고 action을 하도록 배워나갑니다. 
5. 이러한 과정 속에서 최대의 reward를 갖는 action들을 선택하게 되는 optimal policy를 찾아나갑니다.
   

 Bellman Expectation Eqn.이 갖는 의미는 처음에 초기화된 값을 계속해서 다음 value func.의 값들을 가지고 update하며 True value func.으로 다가가는 것입니다. 우리가 동전을 던져서 앞면이 나올 확률이 1/2이라고 어떻게 알았을까요? 동전이 나타낼 수 있는 상태가 앞면, 뒷면 2가지가 있어서 1/2이다 라고 생각할 수 있습니다. 하지만 1/(나올 수 있는 상태)이라는 것을 처음 발견할 때를 생각해보면 직접 무한 번에 가까운 횟수를 던지며 경험적으로 증명하며 깨우칠 수 밖에 없습니다. 즉, 우리가 강화학습을 할 때는 초기화된 initial value(0 혹은 random number)를 여러 과정을 반복하며 얻은 정보들로 update하여 참 값을 얻도록 design되어 있습니다. 그리고 이렇게 반복적으로 얻은 값이 가장 클 때, 우리는 이를 Bellman Optimality Equation이라고 부릅니다.

---

Bellman Optimality Equation

 강화학습에서 우리가 추구하고자 하는 목표는 value func.의 참 값을 찾는 것이 아닌 최대의 reward를 얻는 policy를 찾는 것입니다. 그래서 우리는 이왕이면 가장 큰 참 값을 찾아야합니다. 우리는 어떠한 목표를 이루었을 때, 최적의 상태라고 부릅니다. 그래서 optimal이라는 말이 덧붙여진 단어라면 어떤 목적을 달성된 상태라고 생각할 수 있습니다. 그래서 강화학습의 목표에 따라 찾아진 policy를 우리는 optimal policy라고 부릅니다. 이러한 optimal policy를 따르는 Bellman Eqn.이 바로 Bellman Optimality Equation입니다.

 Optimal value function

 쉽게 생각해보면 Optimal value function이란, 최대의 reward를 갖는 value func.이라고 할 수 있습니다. 따라서 우리는 다음과 같이 2개의 value func.의 optimality를 구할 수 있습니다.

이 중에서 q-func.에 대한 optimal value func.을 구할 수 있다면, 주어진 state에서 q-value가 가장 높은 action을 선택할 수 있게 되고, 따라서 우리는 optimal policy를 구할 수 있게 됩니다. 이렇게 선택된 optimal policy는 다음과 같이 수식으로 쓸 수 있습니다.

< Fig4. Optimal policy >
즉, q-func.을 최대로하는 action만 취하겠다는 의미입니다. 이렇듯 q*(s,a) 을 찾게 되면 우리는 optimal policy를 구할 수 있게 됩니다. 

 Bellman Optimality Equation

 Bellman Optimality Equation은 위 두 optimal value function의 관계를 나타냅니다. 

 

마치며

 강화학습에서는 model을 몰라도 Trial and error를 통해 학습할 수 있게 design 되어있습니다. 여기서 model이란, env.으로부터 주어지는 reward와 state transition probability를 말하는데, 이 말에 의하면 강화학습에서는 Bellman Eqn.을 풀 수 없게됩니다. Bellman Eqn.을 풀기 위해서는 model을 안다는 전제가 있어야하는데 이를 전제하고 푸는 것이 바로 다음 chapter에서 다룰 Dynamic Programming입니다. 강화학습은 이 DP의 한계를 보완하여 발전했기때문에 강화학습으로 넘어가기 전에 DP에 대해서 먼저 알 필요가 있습니다. 다음 포스팅에서는 DP에 대해 다루겠습니다. 

 

오탈자나 잘못 언급된 부분이 있으면 댓글로 지적해 주세요 :)

 

Reference

[1] https://dnddnjs.gitbooks.io/rl/content/bellman_equation.html 

[2] http://www.modulabs.co.kr/RL_library/2621

[3] 이웅원, 양혁렬, 김건우, 이영무, 이의령. "파이썬과 케라스로 배우는 강화학습". 위키북스. p.50-59