RL (강화학습) 기초 - 5. Dynamic Programming

1. Introduce

Dynamic 이라는 것은 연속적으로 발생되는 문제들을 푸는 것을 말하고, Programming 은 개발언어가 아니라 수학적인 문제를 의미합니다. Dynamic Programming 이라는 것은 이렇게 연속적으로 스탭 바이 스탭으로 발생되는 문제를 수학적으로 optimising 해서 풀어내는 것이라고 할 수 있습니다.

어떤 문제는 서브 문제들로 쪼개서 분석할 수 있고 이들을 풀어내는 과정에서 해결이 되는데 크게 두가지로 나눠 볼 수 있겠습니다.

Dynamic Programming 은 풀어내고자하는 문제를 2가지 특성으로 접근합니다.

하나는 Optimal substructure 로서 최적화를 할 수 있다는 것인데 하나의 문제를 2개 이상의 하위문제로 쪼개고 각각을 최적화하게 되면 원래의 문제도 최적화 할 수 있다는 것입니다.

또 하나는 Overlapping subproblems 인데 서브문제들이 여러번 반복적으로 나타나기 때문에 하나의 서브문제를 해결하고 이 결과를 저장했다가 다시 사용하는 것이 가능하다는 것입니다.

이 두가지 특성이 MDP에서도 동일하게 적용이 되고 Bellman equation 과 value function 이 대표적인 특성을 가지고 있습니다.

Bellman equation 이 각 step 별로 연산을 할 수 있도록 해주고 각 step (state) 에서의 value function 은 저장되었다가 다시 연산할때 사용되게 됩니다.

Dynamic Programming 은 MDP의 모든 상황에 대한 것을 이미 알고 있다고 가정합니다. 그렇기 때문에 planning 을 할 수 있게 되는 것이지요. 무엇을 했을때 어떻게 될지 이미 알고 있기에 우리는 계획이라는 것을 미리 세울 수 있는 것과 동일합니다.

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

그리고 MDP를 입력으로 하여 기존의 value function을 더욱 최적화 하는 것이 control 과정입니다.

최종적으로 policy 는 value function을 통해서 생성할 수 있기 때문에 최적화된 value function을 통해서 최적화된 optimal policy를 찾을 수 있게 되겠습니다.

Dynamic Programming이 자주 활용되는 사례와 분야들을 설명하고 있습늬다.

2. Policy Evaluation

이전 내용에서 다루었던 Bellman expectation을 사용해서 반복적으로 연산을 하므로서 policy를 평가할 수 있게 됩니다.

처음 시작되는 v1 은 아마도 모든 states 의 값이 0으로 부터 시작될 것입니다. 하지만 반복적으로 연산이 되면서 값들이 업데이트가 될 것이고 이를 여러번 반복하다보면 어느정도 value 값이 수렴하게 될 것입니다. 이때 수렴된 value들을 사용해서 policy를 만들 수 있습니다.

synchronous backup 이라는 것은 위에서 보는 로직처럼 이전에 사용된 Vk 를 사용해서 다음의 V k+1를 업데이트 하는 방식을 말합니다.

이를 다이어그램으로 표현하고 수학적인 공식으로 표현을 하면 위와 같이 됩니다.

다이어그램처럼 value의 연산이 아래에서 위로 올라가면서 연산이 되기 때문에 back up 이라고 표현합니다. 수식은 이전에 MDP에서 살펴보았기 때문에 어렵지 않으실 것 같습니다.

1~14의 일반적인 states를 가지고 있는 gridworld의 예제입니다. 한번 transition을 할때의 보상이 -1 이 주어지고 회색으로 되어 있는 두개의 terminal states가 존재하는 환경입니다. 액션은 4가지 방향으로의 이동이 가능합니다.

k가 0일때는 모든 states의 value가 0으로 초기화 되어 시작이 됩니다. 각각의 states에 대한 value function의 연산이 되고 다음 k 가 1이 되면 terminal states가 아닌 states들의 value 값이 -1로 되며 이때의 value를 이용해서 policy를 구해보면 오른쪽과 같이 행동이 표기가 됩니다.

이렇게 반복되면서 k 가 3이상이 되면 policy가 최적이 되면서 value 값이 업데이트가 되는 것을 볼 수 있습니다. k 가 무한대로 가면 value 값도 최적화가 되는 것을 볼 수 있습니다.

어느 states에서 시작을 하더라도 현재의 state 보다 큰 값을 가지는 state로 이동을 하게 될 것이고 그 행동을 자연스럽게 policy를 따르게 됩니다. 그리고 계속 이 policy를 따라 이동을 하다보면 terminal state로 가게 되는 것을 볼 수 있습니다.

3. Policy Iteration

policy를 더 좋게 업데이트를 할 수 있는 방법이 없을까? 에 대한 문제를 해결하기 위해서 위와 같이 2가지의 접근 방식을 취하게 됩니다.

먼저 현재의 policy를 통해서 value function을 찾는것을 evaluate라고 합니다.

그리고 이 value 값과 action에 대한 value값을 비교하여 더 좋은 policy를 찾아가는 과정을 improve 라고 합니다.

이 두가지 과정을 반복하여 수행하게 되면 policy와 value가 수렴하게 되고 그때가 최적화 된 policy와 value라고 할 수 있습니다.

evaluation이 수행이 되면서 v 가 업데이트 되어 변경이 되고, 그에 따라 policy를 더 좋은 policy로 업데이트하는 improvement가 수행이 되는 것을 반복적으로 하면서 v*와 PI*로 수렴하게 되는 것을 도식화 하여 보여주고 있습니다.

policy improve 에 대해서 조금더 상세하게 설명하고 있는 내용입니다. 수학적인 기호들이 많이 보이지만 여기서는 어떤 state에서의 value function은 해당 state에서 취할 수 있는 action에 대한 평균값이기 때문에 value function의 값보다 더 큰 값을 갖는 action을 찾아서 취하면 조금더 좋은 policy로 업데이트를 할 수 있다는 내용을 설명하고 있습니다.

더 좋은 q 값을 통해서 개선된 policy를 따르는 value function의 값은 이전의 poilcy를 따르는 value function의 값보다 같거나 크게 될 것입니다.

policy improve 과정이 반복되면서 어느정도 수렴이 하게 되면, 위와 같이 q의 값과 v의 값이 같아지는 지점이 오게 될 것입니다.

이때의 v와 policy는 최적화된 상태라고 할 수 있고 이때의 policy를 optimal policy라고 할 수 있습니다. 우리가 찾고자 하는 목적이기도 하지요.

이렇게 policy iteration이 계속되면 언제까지 반복해야할까요? 끝까지 수렴할때까지 할 수도 있겠지만 너무 오래걸릴 수 있기 때문에 value function의 변화량이 특정한 값 이하가 되면 stop을 하도록 할수 있습니다. 

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

이러한 방법들은 optimal policy를 좀더 빨리 찾을 수 있도록 하는 성능을 개선하는데 유용합니다.

4. Value Iteration

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

첫번째 action이 잘 선택이 되었다면 (첫 단추가 잘 끼어졌다면) 이후의 다음 action들도 최적화될 것으로 생각할 수 있습니다.

그러므로 어떤 state s에서 optimal value가 되었다면 다음 state s'에서도 optimal value가 되었다고 볼수 있게 됩니다.

s' 에서의 optimal value를 찾았다면 이전상태인 s에서의 optimal value도 찾을 수 있게 될 겁니다. 이렇게 마지막 step에서 받은 보상이 뒤로 전달이 되면서 업데이트가 되어집니다.

value가 업데이트가 되는 과정을 보면 위와 같이 됩니다. 앞에서 본 예제에서의 환경에서 한번 step을 이동할때 보상을 -1을 받았기 때문에 위와 같이 마이너스 값이 멀어지면서 커지는 값을 가지게 됩니다.

전체적으로는 policy iteration과 비슷하고 다른 부분은 synchronous backup에서 업데이트를 할때 argmax를 사용하는 것이 아니라 max를 사용해서 한번에 처리가 된다는 것입니다. 그래서 policy를 매번 업데이트 하지 않아도 되게 됩니다.

때문에 때에 따라서는 policy iteration보다 빠르게 수렴을 할수도 있겠습니다.

앞에서 설명한 내용에 대한 다이어그램과 수학적인 공식입니다. max 연산으로 변경된 점이 핵심이 됩니다.

지금까지 배운 내용을 정리한 것입니다. 이러한 방식들을 Synchronous Dynamic Programming Algorithms 라고 하기도 합니다.

기본적으로 value function을 사용하여 하게 되는데 만약 action-value function을 사용하게 되면 연산에 대한 복잡도가 증가하는 것을 볼 수 있습니다.

5. Extension DP

지금까지 배운 동기화 방식과는 다른 비동기화 방식에 대해서 소개하고 있습니다.

Asynchronous Dynamic Programming 은 병렬로 back up이 되는 방식이고 이러한 방식은 연산을 줄이고 수렴을 빠르게 할 수 있습니다.

이러한 비동기 방식을 사용하는 알고리즘이 3가지가 있습니다.

in-place value iteration은 v 값을 하나를 사용해서 처리하기 때문에 불필요한 복사과정이 없습니다. 그래서 더욱 빠르고 효과적으로 업데이트가 되지만 상대적으로 조금 불안정하게 업데이트가 되게 됩니다.

prioritised sweeping 은 Bellman error가 크게 남아있는 states를 backup에 우선순위를 주어 처리되도록 합니다. 방문횟수가 많아지면 업데이트가 최적화에 가깝게 잘되겠지만 방문횟수가 낮은 상태에서는 error가 커지게 될 것이기 때문에 더 많이 업데이트를 하도록 해줍니다.

real-time 방식은 agent가 실제로 경험한 state들에서 sampling해서 업데이트하도록 합니다. 

이러한 DP은 full backup이라고 하는데 모든 케이스를 다 고려해서 최적의 결과를 찾는 방식이기 때문입니다.

이러한 방식은 space가 커지면 커질수록 연산에 시간이 오래걸리고 수렴이 어려워지게 되고 차원이 커지면 커질수록 차원의 저주가 발생하여 어려움이 생기는 단점이 있습니다.

그래서 sample backup을 하는 방법들이 나오게 됩니다.

위와 같은 질문들을 해결하기 위한 방안으로 contraction mapping 이 있다는 것을 보여줍니다.