Planning by Dynamic Programming (by Silver)

오늘 포스트에서는 Dynamic Programming 관점에서 Prediction 및 Control 문제에 대해 간략하게 소개하도록 하겠다. 

 

Dynamic Programming이란, 쉽게 설명하자면 한번에 풀기 어려운 큰 문제를 작은 여러 문제들로 나눠서 푸는 것을 의미한다. Subproblem으로 나눈 후, 그 작은 문제들에 대한 해답을 찾고 그 해답들을 모아서 큰 문제를 해결한다. 

 

Dynamic Programming 방법론이 되기 위해선 아래와 같은 2가지 조건이 필요하다.

1. Optimal Substructure
전체 큰 문제에 대한 obtimal solution이 subproblem들로 나뉠 수 있어야 한다.
2. Overlapping subproblems
한 subproblem을 풀면 그 문제가 다른 쪽에서도 계속 등장한다. 따라서 작은 문제들에 대한 해답들은 cache(잠깐 저장)해두었다가 재사용한다.

이때 Markov decision process(MDP)는 두 가지 성질을 모두 만족하기 때문에, Dynamic programming은 MDP의 상황을 가정하게 된다.

Prediction 문제에 관해서는 MDP와 policy가 주어졌을때, policy를 따를 경우 얻게 되는 value function을 학습하며 이는 최적의 policy와는 관계가 없다. 또한 Control 문제에서는 MDP만 주어졌을때 optimal policy를 학습한다. 이때 S는 State space를, A는 action space, P는 transition matrix, R은 reward, 그리고 γ는 discount factor을 의미한다.

 

1. Iterative Policy Evaluation

Policy를 평가한다는 것은 해당 정책을 따랐을 때, return 값을 얼마나 받느냐를 아는 것이다. 이는 value function을 의미하므로 따라서 Policy Evaluation 문제는 policy를 따랐을 때의 value function을 찾는 문제를 말한다. 앞서 이야기한 용어로 설명하자면, policy evaluation 문제는 prediction인 것이다!

위 슬라이드를 살펴보면, 매 iteration마다, 그리고 모든 state s 에 대하여 Bellman expectation equation을 이용해 모든 value 값들을 업데이트 해주는데, 이를 반복하다보면 prediction에서 궁극적으로 학습하고 싶어하는 value 값은 vπ에 도달하게 된다. 참고로 Bellman equation 수식은 아래와 같다.

(여기서 backup이란, 잠깐 저장해두는 것으로 cache와 비슷한 뜻을 지닌다고 생각하면 좋다)

슬라이드에 나와있는 그림으로 예시를 들어보겠다. 임의의 칸에서 회색 칸인 terminal state로 가는 방법에 관한 prediction 문제가 있다고 가정하자. (Terminal state는 1개로, 그림에서는 마치 두개인 것처럼 그려졌지만, 두 칸 모두 같은 state를 의미한다.) 여기서의 Value는 평균 몇칸을 지나야 terminal state에 도달하는가?가 될 것이다. Terminal State에 도달하기까지의 reward는 모두 1이며, Agent는 random policy를 따르기 때문에 동서남북으로 agent가 이동할 확률은 모두 0.25이다.

우선, Value값이 적혀 있는 Random policy 부분을 먼저 살펴보자. 처음에는 우리가 value를 알 길이 없으니까 쓰레기 값으로 초기화한다. (여기서는 그냥 쉽게 0.0으로 초기화했다.) 16개의 value값들을 모두 한번 업데이트 한것이 바로 k=0->1이며 그 결과 값들은 다음 그림과 같다. 각 value값들이 어떻게 업데이트 되었는지 살펴보기 위해 k=2에서의 2행1열의 값 -1.7을 살펴보겠다. Value값들을 Bellman equation으로 구할 수 있는데 이 문제에서 reward는 -1, discount factor=1, P=1/4이므로 -1+1*(0.25*(-1)+0.25*(-1)+0.25*(-1))=-1.7이 된다. 

이제 Greedy Policy라고 표현되어 있는 화살표가 그려진 그림도 함께 봐보자. policy 그림은 매 iteration마다 새롭게 업데이트 되다가 k=3부터 어떤 특정 정책으로 수렴하는 모습을 볼 수 있다. David Silver 선생님은 다음 강의에서 이를 아래와 같이 이야기 하였다.

우리가 알아야 할 점은 우리는 어떤 주어진 바보같은 policy를 평가만 했을 뿐인데, 평가과정에서 얻은 value function을 가지고 greedy하게 움직이면 결국 optimal policy를 얻을 수 있다.

즉, 다시 말하자면 (1) Random policy에서의 value function을 평가하고 -> (2) 그것에 대해 greedy하게 움직이는 정핵을 만들고 -> (3) 이렇게 얻어진 정책을 다시 평가해 value function을 업데이트하고 -> ... -> 를 만복하다보면 optimal policy로 간다. (이때 greedy하게 움직인다는 것은 무조건 다음 칸 중에 제일 좋은 value 쪽으로 움직이는 것을 말한다.)

이를 정돈하여 설명하면 다음 슬라이드 내용과 같다. 여기서 중요하게 봐야할 점은 이러한 policy iteration은 항상 optimal policy로 결국 수렴한다는 점이다. 이렇게 어떤 iterative한 방법론을 통해 최적의 policy를 찾아나가는 과정인 policy Iteration은 결국 Control 문제라고 생각할 수 있다.