[RL] Markov Decision Process (MDP)

 우선 지난 포스트에서도 소개했다시피 Bellman Equation은 각 칸별로 state에 대한 value를 매김으로써 goal까지 가는 최적의 경로를 계산할 수 있었지만, 계산하는 과정에서 확률적인 부분이 고려되지 않아 조금 적용하기 어려운 부분이 있었다. 이 때문에 경로 계산시 확률적인 요소까지 고려한 방법이 이 포스트에서 소개할 Markov Decision Process (MDP)이다.

Bellman Equation이 가정했던 것은 왼쪽 그림과 같이 Agent에게 위로 가게끔 하면 Agent는 그 지시에 따라서 위로 움직이게 된다는 것이다. 그런데 이렇게 되면 실질적으로 가르치는 사람이 Agent를 조정하는 형식이 되므로, 학습에 대한 의미가 없어진다. 이때문에 방향 선택에 대해 어느정도의 임의성을 부여하자는 것이 MDP의 의미이다. 예를 들어 오른쪽의 그림처럼 Agent에게 위로 가라고 지시를 해도 어느정도의 확률로는 오른쪽으로 갈 수도 있고, 왼쪽으로 갈 수도 있다는 것이다. 그렇다고 위로 가라는 지시가 약해지는게 아니라, 이 지시에 대한 이행 확률 정도로 방향을 표현하자는 것이다. 이렇게 되면 우리가 가지 말아야 할 장애물에 대해서도 어느정도의 확률로 갈 수 있는 가능성이 생기므로 이를 Bellman Equation에 반영할 수 있게 된다. 이렇게 어떤 결정을 내릴 때 일정 확률의 임의성과 일정확률의 결정권자의 의견을 바탕으로 전체적인 의견 결정을 모델링한 수학 모델을 Markov Decision Process라고 표현한다.

 그래서 우리가 표현한 Bellman Equation은 다음과 같았다. 

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

이중 맨 마지막 항목인 V(s')에서 하나의 state가 아닌 여러 state에 대해서 고려를 해야한다. 그러면 V(s')가 아닌
\(V(s_{1}') , V(s_{2}'), V(s_{3}') \) 를 고려해야 한다. 그런데 보통 여러 확률을 고려할 때에는 평균(Expectation Value)를 계산해서 반영하게 된다. 그러면 위의 값을 직접적으로 사용할 게 아니라 \(P(s_{1}')V(s_{1}') , P(s_{2}')V(s_{2}'), P(s_{3}')V(s_{3}') \)을 각각 구한후 더하게 된다. 이걸 하나의 수식으로 정리하면

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

로 표현할 수 있다. 결과적으로 Bellman Equation이 의미하는 바와 같이 각 칸의 State에 대한 Value를 계산하되, 다른 방향으로 갈 수 있는 확률과 State에 대한 Value를 계산해, 그중 가장 최대의 값을 선택하게 끔 Value가 정의되는 것이다. 이렇게 되면 이전 Bellman Equation에서 장애물에 대해 고려하지 않았던 케이스에서 벗어나 확률론적으로 장애물에 대한 reward 계산도 이뤄지게 되므로, 이를 고려한 경로 계산이 가능해진다. 

 이렇게 되면 우리가 이전에 Bellman Equation을 적용했을 때 구한 Value map에서 조금 변하게 된다.

아마 왼쪽이 Bellman Equation을 적용한 결과이고, 오른쪽이 MDP가 적용된 케이스일텐데 잘보면 전체적인 값도 물론이거니와 전체적인 Value 패턴이 변한 것을 확인할 수 있다. 우선 목적지의 바로 옆 값도 그렇고, 장애물 근처의 Value도 상당부분 바뀐것을 확인할 수 있다. 이 모든 것이 다 MDP상에서 장애물에 갈 확률도 존재한 것을 고려했기 때문이다. 

 사실 이게 직접적으로 Optimal한 경로를 구한다기 보다는 뒤에 등장할 Q-function을 구하기 위한 중간과정으로 MDP를 활용하기 때문에 이에 대한 이해가 필요했다. 다른 포스트에서 Q-function을 이용한 Q-learning에 대해서 설명해보고자 한다.

참고 : 

 - Artificial Intelligence A-Z : Markov Decision Process