DRL_Introduction_(4) Value Based Approach_2

https://www.youtube.com/watch?v=dw0sHzE1oAc&list=PLldiB_QS6edl3h831ZrSG8crEWOvPWeun&index=4

 

 

발표자료

https://www.slideshare.net/NaverEngineering/introduction-of-deep-reinforcement-learning

Introduction of Deep Reinforcement Learning

 

 

지난 포스팅내용을 잠깐 정리해보겠습니다.

 

- 강화학습에서 Policy는 State, Action, Reward 세가지 를 이용해서 결정하게 되는데,

Value를 Expected Sum of Future Reward라고 정의하고, 이 Value값에 기반하여 Policy를 정하는 것을 

Value Based Approach에 해당한다고 했습니다.

 

- Value는 Discrete한 상황뿐 아니라 무한개의 Continous한 상황도 잘 다룰 수 있도록

이를 Function으로 구해준다고 하였고, 종류는 State Value Function과 Action Value Function으로 나뉜다고 하였습니다.

즉, 각각

State에서의 Expected Sum of Future Reward,

Action에서의 Expected Sum of Future Reward가 됩니다.

 

- Action Value Function이 필요한 이유는,

State Transition Probability를 복잡한 One step Ahead Search를 통해 구하는 과정 없이

Action Value를 통해 이를 결정하도록 할 수 있기 때문이라고 하였고,

이것은 Model Free 강화학습의 정의에 해당한다고 정리하였습니다.

(Model Based 강화학습은 State사이 관계를 Unsupervised Learning으로 학습한 것)

 

 

 

 

계속해서 Value Based Approach에 대해 정리해보도록 하겠습니다.

 

**** (Bellman Equation을 아직 따로 정리하지 않아서 수식적인 내용은 간단히만 다루고,

추후 Bellman Equation을 다룰때 더 자세히 설명해보도록 하겠습니다.)

 

◆ 목차

◎ Planning VS Reinfocement Learning

◎ Planning

  ○ Exhaustive Search / Dynamic Programming

  ○ Policy Iteration

◎ Learning

  ○ Monte Carlo Method

  ○ Temporal-Difference Learning (a.k.a Reinforcement Learning)

 

 

 

◎ Planning VS Learning

지난 MDP 포스팅에서

'Expected Sum of Future Reward'중

'Expected'를 정의하는 방법론 두가지로 Planning과 Learning를 언급했었습니다. 

예전 포스팅에서는 Prior와 Posterior Probability에 기반해서 가볍게 정리했었는데,

이젠 이 개념을 "State Transition Probability"와 연결해서 좀더 정리해볼 수 있습니다.

 

Value값은 "Expected Sum of Future Reward"값을 말하고, 이 "Expected", 기대값에 대해서

 

선험적인 확률(Prior Probability)을 이용해 기대값을 구해주는 것을 Planning

   => 즉, State Transition Probability를 알고 있거나, 구해줄 수 있는 상황에 적용가능

 

일일이 돌려보면서 관찰된 확률을 기반으로 기대값을 구해주는 것을 Learning이라 합니다.

   => Action Value Function을 이용해 Policy를 결정해줌, State Transition Probability를 구하지않는 알고리즘

 

 

 

*** 

Planning, Learning으로 들어가기전에 Value에 대해 조금 더 정리하고 넘어가도록 하겠습니다.

 

Value는  "Expected Sum of Future Reward"를 말하는데, 

식으로 표현하면 아래 그림과 같습니다.

각 Timestep마다 정의된 Reward값, 그 앞에 Discount Factor를 곱해서 모두 더한것을 

Value값 Gt가 됩니다.

 

=> 여기서 각 Time Step의 Reward값을 구해줄 때는

최종 Reward State값으로 부터

Discount Factor를 적용하여 다른 State와 Action에 Propagate되는 식으로 Reward를 구하게 되는데요,

이를 그림으로 표현하면 아래와 같습니다.

 

◎ Planning 

Planning은

State Transition Probability를 이미 알고있거나, Unsupervised Learning을 통해 구해주는게 가능할 때

쓸 수 있는 MDP 라고 했습니다.

 

○ Exhaustive Search / Dynamic Programming

영상에서는 Planning의 종류를

Exhaustive Search와 Dynamic Programming 두가지로 정리해주셨는데요,

 

Exhaustive Search의 경우,

Time Step별로 State와 State사이 가능한 모든 경우의 수를 찾아서 

이를 직접 일일이 State Transition Probability를 이용해 그 Value값을 구해주는 것을 말합니다.

 

예를들어 

위 그림에서 처럼 4가지의 State가 존재하는 상황에서 T Time Step만큼 벌어질 일의 Policy를 구해야한다고 하면,

4^T만큼의 Value에 대한 경우의 수를 다 Searching해야하는 알고리즘이 됩니다.

 

물론 이 방식같은경우 모든 경우의 수를 Search할수만 있다면 가장 Optimal한 Path를 그려내는게 가능하겠지만,

조금만 State개수가 늘어나고 Time Step이 길어지면 그 복잡도가 계산 불능 수준으로 높아지게 됩니다.

(당연히 아무도 이렇게 접근하진 않습니다.)

 

 

Dynamic Programming의 경우, 이런 복잡도를 낮추기 위해

전체 Step이 아니라, 두 Step 단위로 경우의 수를 풀어서 Value를 계산하는 방식을 말합니다.

그림으로 보면

2스텝 사이의 Value를 계산하는 경우의 수는 4^2  = 16번이고,

이를 T Time Step만큼 반복하면 되는 것이므로, 총 T*4^2번의 연산이 들어갑니다.

복잡도가 4^T에서 T*4^2 로 줄어들게 됩니다.

(Dynamic Programming은 원래 Computer Science Technique인데, 

동적으로 시간에따라 변하는 대상을 Subproblem으로 나눠서 하나하나 계산해나가겠다는 컨셉의 아이디어라고 합니다.)

 

 

○ Policy Iteration

Policy Iteration은

이런 Dynamic Programming을 사용하여 강화학습을 진행한 알고리즘을 말합니다.

크게 Evalutation과 Improvement 두가지 스텝으로 나뉩니다.

먼저 Policy Evaluation을 하고, 그리고 Policy Improvement를 진행하고,

이 두과정을 반복해가며 Policy를 찾아주는 방법인데요, 그림으로 표현하면 아래와 같습니다.

Policy Evaluation은 Value Function을 더 정확하게 수정해주는 것을 의미하고,

Policy Improvement는 수정된 Value Function값에서 가장 Optimal한 Action Path를 Greedy하게 선택해주는 것을 의미합니다.

 

식으로 잠깐 살펴보겠습니다.

 

Policy Evaluation 식

Policy Improvement 식

 

식에대한 자세한 설명은 지금은 일단 Skip하고,

추후 Bellman Equation을 다룰때 다시 정리해보도록 하겠습니다.

 

 

 

아래 블로그에 Dynamic Programming과 Policy Iteration에 관한 내용이 깔끔하게 정리되어있습니다.

한번 참조해보시면 많은 도움 될것같습니다.

https://sumniya.tistory.com/10

[Ch.4] Dynamic Programming

 

 

◎ Learning

앞서 정리했던 Planning,

즉, Model Based 강화학습의 문제점은 환경의 각 State에대한 Transition Probability P(s',r | s,a)를 알고 있거나,

Unsupervised Learning이 가능해야 한다는 것이었습니다.

물론 가능한 사례도 있겠으나, 실제상황에서 불가능 한 경우가 더 많은데,

 

Learning은 이런 환경의 각 State에 대한 Proability를 모르더라도 학습이 가능하도록 만들어진 알고리즘을 말합니다.

 

크게 Monte Carlo Method와 Temporal-Diferrence Learning으로 나뉘는데,

Q-Value를 이용하는 Temporal-Diferrence Learning이 우리가 통상 알고있는 Reinforce Learning알고리즘을 말합니다.

 

○ Monte Carlo Method

먼저 Monte Carlo Method부터 살펴보겠습니다.

Monte Carlo Method는 강화학습 용어는 아니고,

어떤 시뮬레이션이나 Trial의 방법론중 하나로, "반복적인 무작위적 샘플링"의 상황을 넓게 'Monte Carlo' Method,또는 Simulation이라고 부르는 것 같습니다.

https://studyingrabbit.tistory.com/33

몬테 카를로 시뮬레이션(Monte Carlo Simulation) 의 이해 : 원주율값 구하기 (+파이썬 시뮬레이션 코드)

 

위 블로그에 잘 정리되어있습니다.

 

 

강화학습에서의 Monte Carlo Method는

Policy Evaluation진행시 모든 Sample 값을 넣은 것에대한 평균으로 Value를 정하는 방식을 의미합니다.

여기서 말하는 Sample은 학습이 진행된 하나의 의사결정 Trajectory를 말합니다.

가령, 

항상 같은 위치에 시작한다고 했을때,

만약 게임을 1000회 한다면 (1000개의 Samples), 1000가지의 Value Map이 생길 것입니다.

 

이에대해 각 State의 Value값을,

1000개 Sample의 해당 State Value의 평균값으로 구해주는것을  Monte Carlo Method라고 하는 것입니다.

 

 

 

이 Monte Carlo Method 방식에도 문제점이 있는데요,

아래 그림에 정리되어있습니다.

가장 큰 문제점은

반드시 끝이 존재해야 학습이 가능한 방식이라는 것입니다.

Reward에 대한 반응이 목표지점에서부터 Propagate되지 않는 상황이라면 학습이 불가능해집니다.

이런 이유로 시간이 매우매우 오래걸리며, 끝이 존재하는 Episodic Task에만 적용가능하다는 치명적인 단점이 있습니다.

(주식같이 끝이 정해져있지 않은 Continous Task에는 적용할 수 없는 알고리즘이 됩니다.)

 

 

○ Temporal- Difference Learning (Q Learning)

TD Learning은 반드시 끝이나야 학습이가능한 Monte Carlo Method의 단점을 극복할수 있는 알고리즘인데요,

끝이 존재하는 Sample에 대해서만 학습이 가능했던 Monte Carlo Method와 다르게 

한 Sample내에 한 Time Step에서도 어떻게든 학습이 이루어지도록 하는 알고리즘이 바로

Temporal Difference Learning (그중 가장 유명한게 Q Learning)입니다.

 

TD Learning은

 

Monte Carlo Method처럼 환경의 각 State사이의 Transition Probability를 모르더라도 학습이 가능하며,

Dynamic Programming처럼 'Final Outcome'까지 가지 않아도 한 Time Step 사이의 Value를 Update하여 학습이 가능합니다.

 

이러한 의미에서 TD Learning은

Monte Carlo Method의 idea와 Dynamic Programming의 idea를 합친 알고리즘이라고 정리해주셨습니다.