[강화학습 2강] Markov Decision Process

 

이번 강의에서는 위와 같은 순서로 진행되고 Extensions to MDPs는 Silver강의에서도 다루지 않았다.

 

mdp는 environemnt를 표현하는 방법이다.

모든 강화학습 문제는 mdp로 만들수 있다.

markov property는 다음과 같은 성질을 가지고있다.

state가 중요하고 history는 필요없다.

state만으로도 미래를 예측하는데 충분한 정보가 있다.

state transition Matrix는 t state에서 t+1시점의 각 state로 전이될 확률

 

 

simulation을 계속하다보면 transition 확률이 수렴되게 된다.

 

위와 같이 markov process에서 각 episode가 수행될수있고,

당연히 이 환경이 주어진다면  sampling할수있다.

 

이런 process를 행렬(state transition matrix)로 표현할수있다.

 

Markov Reward Process에서는 Markov process에서 Reward와 gamma가 추가됨

Reward는 각 t state에서 다음 t+1 state에서의  reward의 평균

return은 gamma에 따라서 reward에 discount term을 준것.

 

discount을 통해 reward를 수렴하게 만들어 수학적으로 쉽게 다룰수있다.

 

value function은 return 의 기대값!

 

MRP에서 state에 왔을때 각 episode simulation(sampling)의 return 값들을 쭉 수행하고 이로부터 얻은 return들의 기댓값

Gt는 확률변수이다.

 

 

value equation을 관장하는 bellman equation

s 에서의 value를 다음 step의 value로 표현하여 점화식같이 됨.

 

현제 state에서 다음 state로 갈 확률를 곱하고 나서의 다음 state에서의  value function

저 bellman Equation을 state transition matrix를 이용하여 한줄로 표현하면 위와 같다.

 

이를 value로 정리하여 풀어 쓰면 위와 같다.

따라서 I와 P,  R을 알면 value function을 한방에 풀수있다.

큰 MRP문제에서는 computation때문에 반복적인 방법으로 푼다.

 

MDP는 markov reward process에서 Action(Decision)이 추가된 버전임.

 

MDP는 state대신에 action마다 reward가 있음

action을 반드시 특정 다음 state로 가는게 아니라  확률적으로 다음 state로 가게됨.

 

 

policy는 acgent의 행동을 완전히 결정해주는놈

현제 state에 dependent됨

mdp는 environtment,

policy는 agent꺼임

 

이장은 좀 복잡하고 몰라도 되지만 설명하자면,

mdp문제에서 policy가 고정시키면 markov process가 된다.

 

 

MRP와 다르게 MDP에서의 value function은 파이가 있음

두개가 있는데 state value funtion, state-action value function이 있음

Q learning에서 state-action value function을 구하는거임

 

 

 state  value function의 예시를 보면 모든 state에서 다음 action의 확률이 반일때이다.

 

위의 문제를 bellman expectation equation을 통해서 구하는걸 봐보자.

위의 식을 V에서 Q로 바꾸면 아래 식처럼 된다.

action function Q를 이용해서 수식으로 표현해보자면  

V랑 Q랑 어떤 관계라면  위와 같이 표현할수있다.

마찬가지로 Q를 V로 표현할수있음

저 V를 Q로 표현한 자리에 Q를 V로 표현하게끔해서 

V를 V로 이루어진 함수로 만들수있다.

마찬가지로 Q를 Q로 이루어진 함수로 만들수있다.

이게 진짜 작동되는지 확인해볼수있다.

결론은 bellman expectation을 이용한 V를 파이를 따랐을때의 V로만 이루어진 함수로 표현할수있다.

 

이제 optimal policy를 구하는게 목적인데

optimal value funtion은 dmp에서 가장 좋은 방법을 찾는것이다.

gamma가 1일때 optimal value function

optimal action value functoin은 위와 같다.

optimal policy에 대한 정의를 보면

두 policy가 있을때 위의 방법으로 어떤게 더 좋은지 선택할수있다.

위의 optimal policy를 따라가면 optimal value, optimal Q를 따라감.

optimal policy에는 deterministic 한 policy가 있다.

Q optimal 을 안다면 이문제는 풀린거다.

이 optimal을 찾는게 목표인데

이걸 큰문제, 바둑에서는 찾는게 거의 불가능하다.

optimal policy를 bellman equation에 적용해볼것이다.

optimal은 max가 추가되었다.

 

 

이 식은 max때문에 linear 방정식이 아님.

 

bellman optimality Equation은 non linear한 문제이기떄문에 closed form의 정답ㄷ이 없다.

그래서 많이 반복하는 방식으로 문제를 푼다.