DRL_Introduction_(1) Marcov Decision Process_1

아래 영상은 곽동현 연구원님의 1시간 25분짜리 DRL 소개 영상인데요,

Deep Reinforcement Learning에 대한 기본 틀을 잡고 시작하기 딱 좋은 영상이라 생각이들어서,

영상내용을 쭉 정리해보는 포스팅을 진행해보려 합니다

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

 

 

 

정리할 내용이 꽤 많아서

여러 회차에 걸쳐서 포스팅할 것 같습니다

 

 

 

◆ 목차

◎ 강화학습이란?

◎ Marcov Decision Process (MDP)

 

 

 

 

 

◎ 강화학습이란?

인공지능에서 학습의 종류는 크게 

지도학습(Supervised Learning), 비지도학습(Unsuperviser Learnig), 강화학습(Reinforcement Learning)

3가지로 분류가 가능합니다.

 

https://wendys.tistory.com/169

[AI] 머신러닝 지도학습(Supervised Learning) , 비지도학습(Unsupervised Learning) 차이점과 장단점

위 블로그에 개념적인 내용이 잘 정리되어있습니다

 

 

3가지 카테고리의 Learning을 식으로 간단히 표현하면 아래와같습니다.

 

 

의미를 간단히 풀어보면

 

- Supervised Learning

지도학습은 y = f(x) 모델에서 정답 y(label)을 통해 학습시키는 방법으로,

input x가 들어왔을때 적절한 y로 Mapping되는 함수 f(x)를 학습시켜주는 과정이라고 생각할 수 있습니다.

 

- Unsupervised Learning

비지도 학습은 input X에 대한 확률분포 p(x)를 알아내거나 혹은 모델 f(x) 자체를 input x를 통해 찾아내는 방법을 말합니다. 모델에게 정답 y(label)를 알려주지 않는다는 점에서 Supervised Learning과 구분됩니다.

 

- Reinforcement Learning

강화학습은 여기서 조금더 복잡해집니다. 

강화학습은 주변환경 Environment에 반응하여 가장 적절하게 Agent가 행동하도록 학습하는 방법들을 말합니다.

 

강화학습에서는 Agent의 행동양식인 Policy를 결정하기 위해

현재 놓인 상태 'State',  다른 State로 가는 행동 'Action',  Agent의 움직임에대한 보상 'Reward'를 3가지를 정의합니다.

그리고 여기서 Reward 기댓값의 총합 (Expected Sum of Future Reward)이 최대가되는 Policy를 찾도록 합니다.

 

그림으로 표현하면 

 

각 Time Step t마다

- State S(t)는 정의된 Environment에서 표현하는 State Space내에 현재 Agent가 위치한 State를 의미하고,

S(t)∈ S

- Action A(t)는 Agent가 해당 S(t)에서 선택한 Action을 의미하며,

A(t)∈ A(S(t))

- Reward R(t+1)는 "한 Timestep" 뒤에 받게되는 Reward를 의미합니다.

R(t+1) ∈ R

 

즉, 이에따라 Agent가 만들어내는 Trajectory는 아래와 같은 형태를 띄게됩니다

 

 

 

◎ Marcov Decision Process (MDP)

강화학습은 'Expexted Sum of Future Reward'가 되는 Policy를 찾는 것이라고 했습니다. 

여기서 Policy는 MDP(Marcov Decision Process)를 통해 얻어내는 Agent의 행동 양식이라고 할 수 있는데요,

 

Marcov Decision Process는 Policy를 정의하기 위해 쓰이는 수학적 도구라고 보시면 됩니다.

 

 

MDP를 이해하기위해서 영상에서는

 

> Marcov Process,

> Marcov Reward Process,

> Marcov Decision Process 

3단계에 걸쳐서 설명이 진행되고 있습니다.

 

 

- Marcov Process 

먼저, Marcov Process입니다.

예전 선형대수를 공부할때 봤던 Marcov Matrix와 같은 내용이었는데요,

"확률을 이용하여 어떤 객체를 시간에 따라 어떻게 변화할지 모델링하는 것"을 Marcov Chain Probability라고 합니다.

다시말해, 확률분포에따라 이동하는 객체에대한 Stedy State Dirstibution을 알고싶을때 사용되는 기법입니다.

아래 블로그에 이해하기 쉽게 정리되어있으니 자세히 알고싶다면 참고하시기 바랍니다

https://twlab.tistory.com/53

[Linear Algebra] Lecture 24 마코브 행렬(Markov Matrix)

 

 

강화학습에서의 Marcov Process를 적용해보면 아래 그림처럼 생각해볼 수 있습니다.

State Space에서 State내에 전이(Transition)가 확률적으로 일어날때, Steady State Distribution은 어떻게 되는지 알고싶은 것입니다. MDP를 이해하기위해 첫번째로 알고 있어야하는 수학적 개념입니다.

 

 

 

** 선형대수적 내용으로 조금더 정리해보겠습니다. 

Matrix의 Graphical한 의미는, 공간을 'Eigen Vector 방향'으로 'Eigen Value 크기'만큼 압축하는 것이라고 해석할 수 있습니다.

결국 무한번 어떤 Matrix를 곱하게되면 좌표계에 존재하는 모든 벡터들이 Eigen Vector방향으로 Eigen Value비율 만큼 Mapping되는 것으로 수렴하게 되는데요,

 

Marcov Chain와 이 Matrix의 Graphical한 의미를 합쳐서 생각해보면,

 

Matrix를 1회 곱한다는것은 해당 비율만큼 공간을 찌그러트린다는 것.

= Marcov Chain에서 정의된 비율만큼 객체의 성분이 이동한다는 것.

그리고,

Matrix를 무한번 곱하면 벡터가 Eigen vector방향으로 Eigen Value만큼의 비율로 늘어나는것은

Marcov Chain에서도 같은원리로 적용되어서

"무한번 Marcov Process가 반복되었을때 무한번 곱하는 값을 굳이 직접 계산해보지 않더라도,

Eigenvector와 Eigenvalue만 알면 객체의 수렴 비율을 알 수 있다"는 결론이 됩니다.

 

- Marcov Reward Process

앞서 강화학습에는 "State", "Action", "Reward"가 정의되어있어야 한다고 했었는데요,

Marcov Process만으로는 "State"만 설정되어있기 때문에 강화학습을 진행할 수가 없습니다.

 

강화학습을 위해서는 "Reward"와 "Action"이 추가로 정의되어야하는데,

Marcov Reward Process는 Marcov Process에서 단순히 "Reward"개념만 더해진 것입니다.

Marcov Process의 목표가 단순히 Steady State Distribution을 알아내는 것이라면,

Marcov Reward Process는 Expected Reward Ditstribution을 알아내는 것입니다.

즉, State Space에 정의된 각 State에 대해 Expected Reward가 얼마인지 알고싶은 것입니다.

 

- Marcov Decision Process

State, Reward가 정의되었고, "Action"까지 더해진 개념이 바로 Marcov Decision Process (MDP)입니다.

이 MDP를 이용해서 Agent의 Policy를 결정하게 되는데, 그림으로 간단히 표현하면 아래와같습니다.

Marcov Reward Process의 State Transition Probability를 보면, Action이 반영되어 있지 않지만

Marcov Decision' Process의 State Transition Probability에서는 Action이 반영되어있음을 알 수 있습니다.

 

MRP State Transition Probability : P(S'|S)

MDP State Transition Probability : P(S'|S , A)

 

 

또 다른점을 살펴보면,

MRP에서는 Action에대한 정의 없이 그냥 State와 State간 Transition에대한 확률만 정의되어있는 반면,

MDP에서는 Action이 아래와같이 정의되어있습니다.

각 State에서 행할 수 있는 Action이 X,Y두개라고 정의하면,

 

A State에서

X라는 행동을 했을때, 다시 A로 올 확률은 70% , B로 갈 확률은 30%

Y라는 행동을 했을때  다시 A로 올 확률은 90% , B로 갈 확률은 10%

 

B State에서

X라는 행동을 했을때, A로 갈 확률은 50% , 다시 B로 올 확률은 50%

Y라는 행동을 했을때  A로 갈 확률은 80% , 다시 B로 올 확률은 20%

 

 

여기서 Reward를 고려해보면,

A State의 Reward는 +1, B State의 Reward는 -1 로 설정 되어있으므로, A State에 있도록 Policy가 설정되는 것이 더 Optimal한 Agent라고 볼 수 있습니다.

 

내가 현재 A State에 머무르고 있다면, 계속 A에 머무르는게 합리적이므로

70%확률인 X보다 90%확률인 Y라는 행동을 해야 바람직하며,

B State에서는 같은 원리로 Y라는 행동을 해야 더 바람직한 행동이 됩니다.

 

MDP는 Agent가 'Expected Sum of Future Reward'를 최대화 할 수 있도록 하는 행동양식을 만드는데 쓰는 수학적 기법이라고 하였고,

이런 원리대로라면

위 예시에서는 모든 State에서 Y라는 행동만 반복하는 것이 'Expected Sum Of Future Reward'를 최대화할 수 있는 Optimal Policy가 되는 것입니다.

 

 

※ Why "Future" Reward?

지금까지 MDP에서 단순히 Expected Sum of Reward가 최대가 되는 지점이 아니라,  Expected Sum of "Future" Reward에 대해 최대가 되는 Policy를 찾는다고 표현하였습니다. 

여기서 "Future"라는 단어가 내포하는 의미는 바로 다음 Time Step에서의 Reward 최대지점이 아닌,

 앞으로 있을 전체 Time Step에서의 Reward 최대지점을 찾는다는 의미입니다.

 

영상에서는 Karpathy 교수님의 유명한 예제인 Waterworld DQN 예제를 보여주셨는데요,

https://cs.stanford.edu/people/karpathy/reinforcejs/waterworld.html

REINFORCEjs: WaterWorld demo

(영상에서 구현된 예제는 초록색 공을먹는 예제인데, 위 링크랑 조금 다른거 같습니다.)

 

가령

빨간색 공(-1 Reward)뒤에 초록색공(+1 Reward)이 3개가 있다고 하면, 바로 다음 State의 Reward를 최우선 한다면

움직이지 않겠지만, 빨간공을 건드리더라도 초록색 공 3개를 모두 먹는다면 Reward는 +3-1 = +2 로 늘어나기 때문에

앞에 빨간공이 있더라도 움직이는게 더 이득인 경우가 있습니다.

 

영상에서 보여지는 예제에서도 이같은 상황이 잘 나타나는데요,

뒤에 초록색공 무더기를 먹기위해 빨간공으로 달려드는 것을 볼 수 있습니다.

 

 

 

 

 

 

다음포스팅에 이어집니다