동적 프로그래밍을 통한 마르코프 결정 과정

수강일시: 2021.01.20

출처: kmooc SNU048

 

reminder-by-kwan.tistory.com/76

마르코프 결정 프로세스 (Markov decision Processes)

이전 내용인

마르코프 결정 과정에서 value function을 행렬식을 이용해서 구하지 않고 dp를 이용해 시간복잡도를 줄이고자 하였는데 그방식을 소개하고자 한다.

 

dp에 대해 알고있다고 가정하고 진행하지만 다시 리마인드하자면

 

policy가 주어졌을때 V를 구하는 과정을 iterative policy evaluation이라고 한다.

즉 V를 initialize하고 계산의 반복을 통해 V를 수렴하게 한다.

이를 N by N matrix에서 (0,0)또는 (N,N)으로 이동하는 random process에서 적용해보면

다음과 같은 optimal policy를 보이게 된다.

 

다음은 policy improvement를 보도록 하자.

policy improvement는 먼저 주어진 policy를 이용해 V를 구하고 구해진 V를 이용해 초기 policy를 improve된 형태로 다시 구할 수 있는가에 대한 방법론이다.

 

위 예제(small grid prob)에서도 random policy로 시작했지만 V를 구하고나서 optimal policy를 찾게 되었다.

이를 도식화하면 다음과 같다

지금까지 배운 내용을 보자면 다음과 같다.

prediction은  policy가 주어졌을 때 valuefunction을 구하는 과정인데 bellman expectation equation을 이용해 풀고자 하였다. 이번 수업에서는 그중 하나인 iterative policy evaluation를 이용했다.

 

control은 V가 주어졌을때 pi를 구하는것으로 iterative policy evaluation을 통해 구해진 value function을 greedy policy improvement하여 policy를 optimize 한다.

 

이 두 과정의 반복이 policy iteration의 방법이다.