Dynamic Programming (DP)

1. Dynamic Programming
: 연속적으로 발생하는 문제를 수학적으로 optimising 하여 풀어내는 것이다.

 

 

1) DP 문제의 특징

1] Optimal substructure로 최적화 할 수 있다.

: 하나의 문제를 두 개 이상의 하위문제로 쪼개고 각각을 최적화 하게 되면 원래의 문제도 최적화 할 수 있다.

 

2] Overlapping subproblems

: Sub problems가 여러번 반복해서 나타나기 때문에 하나의 sub problem을 해결하고, 이를 저장했다가 다시 사용하는 것이 가능하다

 

- MDP에서도 이 2가지 특성은 동일하게 적용된다.
-> Bellman equation과 value function이 대표적인 특성을 가지고 있다.

=> Bellman equation이 각 step 별로 연산을 하게 해준다.

=> Value function은 각 step에서 저장되었다가 다시 연산할 때 사용된다.

 

 

 

2) Planning
: DP는 MDP의 모든 상황에 대해 이미 알고 있다고 가정한다.

 

- MDP와 policy를 입력으로 하여 value function을 찾아내는 것이 prediction 과정이다.

 

- 최종 적으로 policy는 value function을 통해 생성하므로 최적화된 value function을 통해 최적화된 optimal policy를 찾을 수 있게 된다.

 

 

 

2. Policy Evaluation

1) Bellman expectation을 사용해서 반복적으로 연산을 하면서 policy를 평가할 수 있게 된다.

 

- 처음 시작되는 \( v_1 \)은 모든 states의 값이 0으로 부터 시작될 것이다. (아마도?)

-> 반복적인 연산으로 값들이 없데이트되며 value값이 수렴한다.

=> 수렴된 value들을 사용해서 policy를 만들 수 있다.

 

 

2) Synchronous backup 이라는 것은 위의 process 처럼 이전에 사용된 \( v_k \)를 사용해서 다음의 \( v_{k+1} \)을 업데이트 하는 방식이다.

 

- 이를 다이어그램과 수학 공식으로 표현하면 위와 같다.

 

- Value 연산이 아래에서 위로 올라가면서 연산 되기 때문에 back up 이라고 표현한다.

-> 수식은 MDP에서 살펴보았다.

 

 

3) 1~14의 states를 가지고 있는 gridworld의 예제이다. 한번 transition을 할 때 보상이 -1이 주어지고, 회색으로 되어 있는 terminal state가 2개 존재하는 환경이다.

-> Action은 4가지 방향으로 이동이 가능하다.

 

 

 

 

4) \(k\)가 0일 때 모든 state의 value가 0으로 초기화 되어 시작된다.

 

- 각각의 states에 대한 value function 연산이 된 다음, \( k\)가 1이 되면 terminal states가 아닌 states들의 value 값이 -1로 된다. 

-> 이때, value를 이용해서 policy를 구해보면 오른쪽과 같이 행동이 표기된다.

 

- 이렇게 반복되면서 \( k\)가 3 이상이 되면 policy가 최적이 되면서 value 값이 없데이트 되는 것을 확인할 수 있따.

 

- 어느 점에서 시작했든 현재의 state 보다 큰 값을 가지는 state로 이동하여 자연스럽게 policy를 따르게 된다.

 

 

 

 

3. Policy iteration

 

1) Policy를 더 좋게 갱신하는 2 가지 접근 방식

 

- evaluate : 현재의 policy를 통해서 value function을 찾는 것을 evaluate라고 한다.

 

- improve : 위의 value 값과 action에 대한 value 값을 비교하여 더 좋은 policy를 찾아가는 과정이다.

 

-> 위의 두 과정을 반복 수행하면 policy와 value가 수렴하게 되고, 그때가 최적화된 policy와 value라고 할 수 있다.

 

 

 

 

 

2) Policy improve

 

- 어떤 state에서의 value function은 해당 state에서 취할 수 있는 action에 대한 평균값이기 떄문에 value function의 값보다 더 큰 값을 갖는 action을 취하면 더 좋은 policy로 update할 수 있다.

 

 

3) Policy iteration

 

- value function의 변화량이 특정한 값 이하가 되면 stop을 하도록 할 수 있다.

 

- 또는 매 iteration 마다 policy improve를 하면 비용이 커지므로, 간단하게 k 가 몇 번 반복된 이후에 한번 improve 하도록 할 수 있다.

 

 

 

4. Value iteration

 

- Optimal policy는 첫번째 action이 최적화 되는 부분과 전체적인 action들이 최적화 되는 부분으로 나누어 볼 수 있다.

-> 첫번째 action이 잘 선택되었다면, 다음 action들도 최적화 될 것으로 생각할 수 있다.

=> 어떤 state (1)에서 optimal value가 되었다면, 다음 state s (2)에서도 optimal value가 되었다고 볼 수 있다.

 

 

- 반대의 경우에도 동일하다.

-> state (2)에서 optimal value를 찾았다면, state (1)에서도 optimal value를 찾을 수 있다.

=> 마지막 step에서 받은 보상이 뒤로 전달 되면서 update 되어진다.

 

 

-> 마이너스 값이 terminal state에서 멀어지면서 커지게 된다.

 

 

 

- 전체적으로 policy iteration과 비슷하고, synchronous backup에서 갱신할 때 argmax를 사용하지 않고 max를 사용해서 한번에 처리한다.

-> policy를 매번 update하지 않아도 되고, policy iteration 보다 빠르게 수렴 할 수도 있다.

 

-> 앞서 설명한 value iteration의 다이어그램과 공식이다.

=> max로 변경된 점이 핵심이 된다.