[RL] The Bellman Equation

  Richard Ernest Bellman이 제안한 Bellman Equation은 이전 포스트에서 잠깐 소개했던 State와 Action, reward(+ discounted value)를 이용해서 특정 값으로 도출하는 공식으로, 강화학습에서 거의 처음으로 나오는 주제이다. 처음 이 공식이 나왔을 때는 복잡한 조건이 담긴 문제에서 해를 구하는 Dynamic Programming의 기법 중 하나로 쓰였었고,  지금에 이르러서는 강화학습에 많이 활용된다. 이 공식이 어떤식으로 이뤄지는지 간단하게 설명해보고자 한다.

 보통 강화학습 강좌를 보면 이런 도식판을 많이 보게 된다.

좌측 하단에는 로봇이 하나가 있고, 우측 상단에는 이 로봇이 도달해야 하는 목표가 있다. 그런데 이 목표의 아래에는 장애물도 하나 있고, 애초에 접근할 수 없는 곳도 존재한다. 과연 이 로봇이 장애물을 피해서 목표까지 도달할 수 있을까?

 사실 직관적으로 생각해볼때 이 로봇을 일일이 조정하면서 목표에 도달하게 할 수 있다. 항상 유저가 개입하면서 모서리에 도달하면 방향을 틀도록 하고 앞에 장애물이 있으면 피하고 다른 방향으로 피하게 하면서 목표에 도달하게끔 할 수 있다. 보통 이렇게 경로를 사전에 계획(plan)하고 진행함으로써, 로봇이 목표에 도달하게 할 수도 있다. 그런데 이런걸 인공지능이라고 할 수 없다. 인공지능이라 함은 유저가 항상 개입할 필요없이 로봇이 스스로 경로를 탐색하고 장애물을 피해가 가게끔 학습이 이뤄져야 한다. 예를 들어 위와 같은 케이스에서도 로봇이 어디에서 출발하건, 위의 지도의 모양이 바뀐다 할지라도 로봇이 스스로 목표를 인지하고, 찾아갈 수 있게끔 명확한 규칙(Policy)이 있어야 한다. 

 우선 이전 포스트에서 소개한 바와 같이 학습하는 주체에게 정보를 알려주기 위해 각 칸별로 reward를 매겨본다. 참고로 보통 위와 같이 뭔가 끝이 나는 조건이 있는 케이스에선 목표를 reward 1, 회피해야 할 장애물에 대해서는 reward -1을 주게 된다. 그리고 경로를 찾으면서 얻는 reward를 모아 비교해보게 된다. 이렇게 되면 상대적으로 장애물을 거친 경로는 기본적으로 reward -1을 감수하기 때문에 안 가친 경로에 비해서 reward가 낮게 되고, 학습시 해당 경로는 배제하게 될 것이다. 

 이런 식으로 각 칸 별로 reward를 계산해서 특정 state에 대한 Value를 mapping시켜놓은 함수가 이전에 잠깐 소개했던 Value-state function, 이제 이장에서 소개할 Bellman Equation이다. 수식으로는 다음과 같이 표현된다. 

$$V(s) = \underset{a}{\max}(R(s, a) + \gamma V(s'))$$

 이 함수가 의미하는 것은 특정 s (state)일 때의 행동(a)에 대한 reward를 계산하고, 다음 State에 대한 Value를 구이용해서 현재 state에 대한 value를 구하되, 위의 케이스 처럼 취할 수 있는 action의 경우의 수가 많으므로 그중 가장 최대의 value를 가지는 값으로 action을 취하면 그게 바로 해당 State의 Optimal Value라는 것이다. (max 아래 a표시가 되어 있는 것이 그런 의미를 지니고 있다.) 그런데 위 수식을 잘 보면 다음 state의 value에 $$\gamma$$가 들어 있는 것을 확인할 수 있다. 이게 무엇을 의미할까? 

 일단 이 값은 discount factor라고 강의에서 소개하고 있고, 내가 제대로 알고 있는지는 잘 모르겠지만, 일단 내가 이해한 바로는 목표로부터 어느정도 거리가 있음을 나타내는 일종의 상수라고 알고 있다. 왜 그런지는 앞에서 소개했던 map을 다시 살펴봐야 한다.

 조금전에도 소개한 것과 같이 bellman equation을 이용해서 해당 칸의 value를 구하기 위해서는 현재 state상에서 action을 취했을 때의 reward와 다음 state의 value값이 필요하다고 언급했다. 그런데 현재 우리한테 주어진 정보는 목적지와 장애물에 대한 reward 값만 있다.그럼 결국 이 전체의 각 칸별로 state에 대한 value 값을 구하기 위해서는 결국 목적지에서부터 거꾸로 계산하면서 돌아가야 한다는 것이다. 결국 파란 화살표가 있는 부분은 오른쪽으로 갔을 때 목적지에 도달할 수 있으므로, 이때의 reward를 감안해서 V=1이라는 값을 계산할 수 있다. 그런데 discount factor가 없게 되면 goal에서 가깝든 멀든 모든 값이 전부 Value값을 1로 가지게 되므로, 우리가 추구하고자 했던 방향에 대한 정책을 세울 수 없게 된다. 그래서 역으로 계산하면서 goal로부터 얼마나 멀어지는지를 감안할 수 있는 factor가 바로 discount factor라고 생각했다. (아니라면 답변을 달아주시길...) 아무튼 discount factor가 0.9라고 가정한 상태에서 전체 map에 대한 V(s)를 구하면 다음과 같이 된다.

 잘 보면 알겠지만 흰칸의 reward가 다 0이기 때문에 결국 다음 state의 value만으로 이전 state의 value를 계산하게 되고, 이때 discount factor가 곱해지면서 왼쪽 하단까지 이르게 된다. 여기까지 오면 나머지 빈칸은 어떻게 채우냐는 궁금증이 생길 수 있다. 사실 바로 앞에서 구한 것과 동일하다. Bellman Equation에 따르면 어차피 V(s)는 optimal value를 가지는 action만 선택하게 되므로, 아래쪽으로 가는 방향도 위쪽 방향과 동일하게 다음 state의 value에 discount factor만 곱해져서 구해진다. 결국 Bellman Equation에 의해서 구한 각 칸의 state에 대한 Value는 다음과 같이 정의된다.

 이렇게 되면 로봇(or agent)이 V(s)가 증가하는 방향으로만 움직이게끔 설정된다면, 원하는 목표까지 도달할 수 있을 것이다. 

 그런데 아마 이상한 점이 있을 것이다. 우리가 애초에 reward를 계산할 때, goal에서는 1, 장애물은 -1을 주기로 했는데, 지금까지 보면서 reward가 -1인 것은 전혀 고려가 되지 않았다. 결국 위와 같은 방식으로 구한다면, 우리는 장애물에 대한 reward 없이도 goal 의 reward만 가지고 로봇의 이동 경로를 설정할 수 있게 된다. 사실 여기엔 우리가 한가지 무의식적으로 가정한 부분이 있다. 로봇이 꼭 우리가 지시한 방향으로만 간다고 생각한 것이다. 보통 이런 방식을 결정론적(deterministic)이라고 한다. 그런데 뭔가 학습이라는 게 이뤄지려면 이전 포스트에서 다뤘던 trial-and-error 방식처럼 장애물에 실제 접촉하면서 얻은 error를 최소화 하는 것과 같이, 로봇이 실제 잘못 움직인 케이스도 고려되어야 한다는 것이다. 이를 위해서는 뭔가 결정론적으로 접근하는게 아닌 확률론적(stochastic)으로 동작해야 한다. 간단히 말해 로봇이 goal을 향해 가면서도 특정확률로는 장애물로 가는 확률도 고려되어야 한다는 것이다. 이런 식으로 Value-state function에 확률적 개념이 들어간 것이 바로 MDP라고 불리는 Markov-Decision-Process가 된다. 이에 대해선 다음 포스트에서 소개해보고자 한다.

참고:

 - Artificial Intelligence A-Z : The Bellman Equation