단단한 강화학습 Chapter4_동적 프로그래밍 (Dynamic Programming)

"Dynamic Programming"이라는 용어는 MDP(Marcov Decision Process)같은 환경모델이 완벽하게 주어졌을때

-> State간의 Transition Probability와 그에 대한 Reward Funvtion이 완벽하게 정의되어 있을때

최적 정책을 계산하기위해 사용될 수 있는 일군의 알고리즘을 가리킵니다.

 

고전적인 DP 알고리즘은 기본적으로 환경에대한 Modeling이 완벽해야한다는 점과,

엄청난 양의 계산량을 필요로 하기때문에 그 활용도가 제한되지만 이론적으로는 현재까지도 중요한 위치를 차지합니다.

 

이번 Chapter4 에서 정의하는 환경은 

Finite(유한) Marcov Decision Process 로 모델링된다고 가정합니다.

-> 환경의 상태 S, 행동 A, 보상 R의 집합이 유한집합이고,
환경내에서 (상태-행동 쌍에 대한 그 다음상태-보상)의 모든 Transition Probability가 정의되어있는 상태

s,a에대한 s`,r의 Transition Probability

 

※ 참고

유한 MDP라는 것은, State와 Action이 Continous(연속된)한 것이 아니라 Discrete(이산적인)한 것을 의미합니다.

DP의 개념을 이러한 유한 MDP가 아닌, 상태와 행동이 Continous한(=무한한) MDP에도 적용할 수는 있으나,

정확한 해는 특별한 경우에만 구할 수 있다고 합니다. 보통 상태와 행동의 공간을 양자화(quantize)하여 유한 MDP를 적용하는 것이라고 하는데, 챕터 9에서 주로 다루게 될 내용이라고 합니다.

 

 

 

 

DP와 강화학습의 핵심개념은 좋은 정책을 찾는 과정을 체계적으로 구조화 하기위해

Value Function을 이용한다는 점입니다.

책의 3장에서 정리됐던 내용은 일단 Optimal State/Action Value Function이 구해지고 나면,

나머지 최적 정책은 쉽게 구할 수 있다는 것이었습니다.

 

즉, 4장에서는 두가지 차원에서 문제를 바라봐야함을 알 수 있는데

한가지는 Value Function에 대한 것이고, 다른 한가지는 Policy에 대한 것입니다.

 

여기서

"현재 Policy에서 가장 Optimal한 Value Function을 어떻게 구할 것인가?"는 Policy Evaluation에 해당하고,

"현재 취하고있는 Policy는 가장 Optimal한 Policy인가? 아니라면 어떻게 더 향상시킬 것인가?" 는 Policy Improvement

에 해당합니다.

 

 

◆목차

◎ 정책 평가(예측) (Policy Evaluation(Prediction))

◎ 정책 향상 (Policy Improvement)

◎ 정책 반복 (Policy Iteration)

◎ 가치 반복 (Value Iteration)

◎ 비동기 동적 프로그래밍 (Asynchronous Dynamic Programming)

◎ 일반화된 정책 반복 (Generalized Policy Iteration)

 

 

 

 

◎ 정책 평가(예측) (Policy Evaluation(Prediction))

Policy Evaluation (정책 평가)이란,

정책 π에 대한 상태가치함수 Vπ를 계산하는 방법을 말합니다.

챕터 3장으로부터 기억을 되살려서 Value Function에 대한 Update과정을

아래와 같이 진행하였을때,

k → ∞로 접근할때 Value Function은 Vπ로 수렴하게 됩니다.

 

※ 참고

여기서 π(a | s)는 정책 π에 있을때 State s에서 Action a를 취할 확률을 의미하고,

p(s`, r | s, a)는 환경의 모델링으로부터 정의된 State간 Transition Probability를 의미합니다.

책에서는  Discount Factor γ가 1보다 작은 값이거나, Policy π를 따르는 모든 상태가 종국적으로 더는 변하지 않는 상태에 도달한다는 것이 담보된다면, Vπ의 존재와 유일성은 보장된다고 합니다.

 

근사값 Vk로부터 Vk+1을 구할때, 모든상태 s에게 동일한 방식으로 구해주는데,

State s의 현재 Value와 현재의 보상의 기대값을 이용하여 구하게됩니다.

이 계산과정을 기대값 갱신 Expected Update라고 부릅니다.

 

 

* 여기서 한가지 짚고 넘어갈 부분이 있습니다. 3장 연습문제를 풀면서도 들었던 의문점인데, 

기대값을 갱신할때, 앞선 State의 갱신값을 그대로 사용해서 그때그때 바로 새로운 Value를 계산할 것이냐,

아니면 k단계와 k+1단계 각각의 Value Array를 만들어서, 이전가치를 모두 보존한채

일괄적으로 모든 State에 대해 Value Update를 진행할 것이냐를 정해야 하는 문제입니다.

 

정답은 어느쪽도 틀린것은 아니나(둘다 Vπ로 수렴), 전자의 방식이 더 빨리 수렴합니다.

새로운 데이터가 생기자마자 바로 이용할 수 있기 때문입니다.

이 책에서도 DP 알고리즘에 대해 말할때는 대부분 전자의 방식을 사용합니다.

Pseudo Code는 아래와 같습니다.

 

◎ 정책 향상 (Policy Improvement)

지금껏 살펴본 Policy Evaluation은 임의의 Deterministic Policy π에 대해서 가치함수 Vπ를 결정하는 방법을 의미합니다.

Policy Improvement는 이 Policy를 변화시켜야 할지 그대로 두어야 할지를 정하는 작업을 의미합니다.

 

한가지 방법은, 해당 State s에서의 Policy가 a ≠ π(s)일때, 

해당 State에서 a를 선택해보고, 그 이후의 Step을 π을 따르도록 하는 것인데,

이런식으로 행동하는 것을 아래와같이 Action Value Function으로 표현해볼 수 있습니다.

해당 State에서 a를 선택해보고, 그 이후의 Step을 π을 따르도록 하는 Policy를 π`라고 했을때,

만약 아래의 부등식을 만족한다면, 

정책 π`은 π만큼 좋거나, 더 좋은것임에 틀림없으므로, 

π`로 Policy를 변경해주어야 합니다. 이를 Policy Improvement라 부릅니다.

 

아래는 Policy Improvement에 사용된 위의 부등식의 증명과정입니다.π`가 위의 부등식을 만족할때 "Sum Of Expected Reward"이 π보다 더 크다는 것에대한 증명인데, 간단히 참고해보면 되겠습니다

State하나에 대해서 더 좋은 Policy를 찾는 과정은 이러한데,

이것을 확장시켜서 '모든 State'에 대해서, 그리고 선택가능한 '모든 Action'에 대해서 Policy Improvement를 진행하려면 어떻게 해야할지 살펴보도록 하겠습니다.

 

책에서는 이를 Greedy하게 (최대값을 Deterministic하게) 결정하는 Deterministic Policy에 대한 방식만 다루고 있는데, 

State s에서의 Policy π에 대해서, 가능한 모든 (Action) a와 모든 (그 다음 State) s`에 대해서 가장 Value가 큰 것을 Greedy하게 선택해주는 Policy에대한 식은 아래와 같습니다. (만약 같은 Value인경우 둘중하나를 랜덤하게 선택)

만일, 새로운 Policy

π`에 대해서 기존 Policy보다 못하거나 같은수준의 Policy가 될경우,

Vπ = Vπ`으로 변동이 없을 것이고 아래와 같은 관계가 성립하게 됩니다.

-> Policy 변동이 없는 그냥 Value계산식과 같아집니다.

 

 

◎ 정책 반복 (Policy Iteration)

가치함수 Vπ를 이용해서 Policy π를 더 좋은 Policy π`로 향상시키면,

π`에대한 가치함수 Vπ`를 계산하고, 다시 이 가치함수 Vπ`를 이용해 더 좋은 정책 π``를 계산할 수 있게됩니다.

 

이러한 Improvement와 Evaluation의 반복과정을 'Policy Iteration (정책반복)'라고 부릅니다.

E는 Evaluation, I는 Improvement

 

* 이렇게 Policy에대해 Evaluation과 Improvement를 반복하는 과정은 강화학습 전반에서 중요하게 다루게되는 구조입니다

 

 

*참고

Policy Evaluation는 그자체가 Iterative한 계산과정이며,

Policy Iteration에서 Policy Evaluation은 매 Step마다 이전 Policy의 Value Function으로부터 시작됩니다.

Policy Improvement과정을 통해 한 Policy 에서 더 좋은 Policy로 정책이 바뀔때,

그 가치함수는 사실 거의 변하지 않으므로, 이러한 Policy Iteration에서 Policy Evaluation의 수렴속도가 아주많이 증가하게된다고 합니다.

Policy Iteration Pseudo Code

 

 

◎ 가치 반복 (Value Iteration)

Policy Iteration에서

Policy Evaluation과정은 Policy π에 대한 상태가치함수 Vπ를 계산하는 것으로, 완벽히 수렴하려면 

여러번의 Iterave한 연산이 필요하게됩니다. 

 

Policy Iteration의 매 Iteration마다 이러한 시간이 오래걸리는 Policy Evaluation을 진행하는것은 

Policy Evaluation

Policy Evaluation은 Iterative한 연산과정으로, 이론상 Vπ로 정확하게 수렴하기 위해서는 무한대의 반복이 필요합니다.

당연히 이렇게 오래기다리지는 않고, Policy Evaluation을 중도에 끊고 다시 Policy Improvement과정을 갔다와야하는데,

여기서 'Policy Evaluation을 언제 끊어야 하는가?'에대한 여러가지 방법들이 존재합니다.

 

가치반복이란 바로 이러한 방법론중 하나로,

Policy Evaluation계산과정을 오직 한번의 Update만 진행하고 다시 Policy Improvement를 진행하는 것을 말합니다.

 

Policy Improvement와 중단된(Truncated) Policy Evaluation를 결합하여 아래와같이 Value Iteration알고리즘을 표현할 수 있습니다.

 

위는 Value Iteration의 Pseudo Code로,

Value Function의 변화가 아주 작아지면 Iteration을 멈추는 식으로 구현되어있습니다.

 

 

 

 

Value Iteration은 

Policy Iteration의 매 Step의 일괄과정에서 

Policy Evaluation의 일괄계산과 Policy Improvement의 일괄계산을 효과적으로 결합한 것이라 볼 수 있습니다.

 

Policy Improvement 사이사이 Policy Evaluation 과정을 한번이 아니라 여러번 함으로서 더 빨리 수렴하게 할 수 있습니다.

=> 이런경우 일부는 Truncated Policy Evaluation에서의 Value Function을 통해 가치함수가 Update되고,

일부는 Value Iteration에서의 Value Function을 통해 가치함수가 Update되는것입니다. (앞서 Policy Evaluation을 오직 한번의 Update만 하는 Policy Iteration을 Value Update라 하였으므로,)

 

 

 

 

 

 

 

 

 

 

 

◎ 비동기 동적 프로그래밍 (Asynchronous Dynamic Programming)

위에서 정리한 일반적인 동적 프로그래밍 방법의 문제는,

MDP 전체과정에 대해 Planning을 진행 하다보니,

상태집합이 커질경우 그 계산량이 어마어마 하다는 것이었습니다.

 

Asynchronous Dynamic Programming, 비동기 동적 프로그래밍 알고리즘은 상태집합에 대해 일괄계산(systematic-sweep)이아닌, 일부분씩 (in-place) iterative 연산을 하는 알고리즘으로,

상태의 가치를 갱신하는 순서가 무엇이든 개의치 않고, 다른상태의 가치를 이용할 수 없는 상황이라면 그 값이 무엇이든 다른 상태의 가치를 이용하여 해당상태의 가치를 갱신합니다.

 

비동기적 동적 프로그래밍에서는 어떤 상태의 가치가 한번 갱신될 동안 다른 상태의 가치는 여러차례 갱신될 수도 있습니다.

 

정확하게 가치를 수렴하도록 하기위해서는 모든 상태의 가치가 갱신될 때까지 갱신을 계속 수행해야 하므로,

in-place 갱신과정이 어느정도 진행된 후에는 전체에대한 일괄 갱신을 수행합니다.

-> 비동기적 동적프로그래밍은 이런식으로 갱신할 상태를 선택하는데 있어서 유연하게 대처하는 모든 알고리즘이라고 넓게 받아들이면 될것 같습니다.

 

가령, Policy Improvement와 Evaluation을 반복하는 과정속에서,

Evaluation 과정(State의 가치갱신)을 오직 한번만 하고 Improvement를 진행하는 것을  Value Iteration이라고 했습니다.

이때 Evaluation 과정이 모든 State에 대한 것이 아니라, 일부분만 선택에 의해서 비동기적으로 갱신을 진행할수도 있는 것입니다. (일부가 합쳐져서 결국 나중에 전체에대한 갱신이 이루어져 수렴한다면, 상관없다는 것입니다.)

 

 

 

 

◎  일반화된 정책 반복 (Generalized Policy Iteration)

Policy Iteration은 동시에 서로 작용하는 두가지의 과정

- 가치함수가 현재의 정책을 잘 따르도록 하는 것 : Policy Evaluation(Prediction)

- 정책을 현재의 가치함수에 대한 탐욕적 정책으로 만드는 것 : Policy Improvement

을 번갈아가며 진행한 것을 말합니다.

 

여기서, Policy Evaluation과정을 딱 한번씩 진행할경우 Value Iteration라고 하며,

비동기적인 동적프로그래밍에서는 한번에 전체가아닌 일부분씩 State Value를 갱신할 수도 있습니다.

 

Policy Evaluation과 Policy Improvement의 반복주기, 그리고 위와같은 세부사항에 관계없이

이 두 과정이 서로 상호작용하게 하는 일반적인 모든 방법을 GPI(Generalized Policy Iteration)라는 용어로 책에서는 사용합니다.

 

거의 모든 강화학습 방법은 GPI로 설명이 가능합니다.

 

위 그림처럼, Policy는 항상 가치함수를 기준으로 향상되고,

가치함수는 해당 Policy에대한 값으로 수렴하게됩니다.