강화학습 학습하기 - [2] MDP

[2] Markov Decision Process (MDP)

"강화학습 학습하기"시리즈는 KAIST 신하용 교수님의 수업 IE540 "DP and RL"수업 내용을 제가 제 방식대로 요약 및 정리한 것입니다. 퍼가실때는 미리 물어봐주시고, 내용은 제가 변형하고 추가하되 렉쳐노트에 쓰인 그림은 사용해도 된다고 교수님께 허락 받았습니다. 

There are no stupid Questions, only stupid Answers.
 (세상에 이상한 질문은 없다, 오직 이상한 대답만이 있을뿐이다.)
질문은 언제나 환영입니다. 

0. Previously on..

저번 1편에서는 기계학습이 무엇인지에 대해서 알아보고 강화학습은 그것과는 어떻게 다른지 알아봤다. Data - driven learning이 아니라 환경과의 interaction을 통해서 학습되는 것이다. RL의 중요한 요소들인 model,reward 등을 알아봤고, Markov Decision Process에 알아봤다. 이번 편은 저번에 언급한 MDP를 더 자세히 다룰예정이다. MDP문제를 우린 DP로 푸는 것을 3편에, 그 이후에는 RL로 푸는 것을 할 것이기 때문에 MDP에 대한 이해가 선행되어야한다. 

1. Markov process (Markov chain)

Markov Process: A Random process with Markov property. Markov property = Memoryless property

Markov process는 Markov property를 가진 random process이다. Markov property는 위에 있는 식처럼, past의 상태와 present의 상태가 future의 상태에 영향을 주는 것이 아니라 오직 현재 상태만이 future state(next state)에 영향을 주는 것이다. 이를 다르게 부르면 "memoryless property"라고도 한다. Next state가 previous state에 대해서 독립이면 memoryless property를 가졌다고 볼 수 있다. 

Tuple로 정의하는데, MP는 <S,P>로 표현한다. 여기서의 S는 (finite) set of states S = {1,2,3,...,n}이며, P 는 a state transition matrix이다. 이때의 P_i,j = p(S_t+1 = j | S_t = i )이다. 현재 상태가 i - state일때, next state가 j - state일 확률을 모은 행렬이 바로 state transition matrix이다. 

State transition matrix

2. State of an MP

State는 크게 세 가지로 나눠진다. 첫 번째는 transient이며 이 상태는 다른 곳으로 이동하는 상태이고, 두번째는 recurrent이며 이 상태는 next state가 자기 자신이다. 마지막으로 Absorbing state는 transitient가 끝난다. 종결조건인 것이다. 

 Ergodic MP란 state들이 recurrent하고 aperiodc하기 때문에 시간이 무한하다면 fully exploration이 일어나는 MP이다. Ergodic이라는 말은 동역학의 궤적이 거의 항상 공간 전체를 채우는 성질인데, ergodic MP도 같은 의미이다. Aperiodic때문에 시스템이 cycle이 없고, recurrent하기 때문에 각각의 state에 무한번 방문할 수 있다. 

 또한 Limiting distribution d_i는 state distribution이 결국 시간이 무한히 흐르면 어딘가로 수렴한다면 그때의 state distribution을 말하는 것이다. 이때 중요한 성질이 그렇게 수렴하고 나면 state transition matrix를 곱해도 똑같이 limiting distribution이 되어야한다. 이때의 d = dP 값은  P에 대한 eigenvector를 구하면 쉽게 값을 찾을 수 있다. 

Limiting Distribution

3. Markov Reward Process (MRP)

3-1. MRP

MRP는 Markov process에 상태와 관련된 reward values를 결합한 process이다. MRP도 tuple로 정의하는데, <S,P,R,gamma(discount factor)>이다. 

MRP

S,P는 동일하지만, state에 dependent한 reward가 생겼고, reward를 return으로 계산하는 discount factor도 구성요소에 들어간다. (Discounted) Return은 reward의 discount factor의 exponential summation이기 때문에, 아래 식처럼 표현할 수 있고, gamma가 0에 가까울 수록 근시안적인(myopic) 고려를 만들고, gamma가 1에 가까울 수록 너무 먼 미래를 고려하게 된다. 근시안적인 reward말고 더 큰 보상을 기다릴수도 있으며, 미래에 대한 불확실성으로 discount factor를 고려한다. 또한 수학적으로도 매우 편리한데, discount factor가 있으면, continuing task라도 return이 무한대가 되지 않고 수렴하게 된다. 그렇다고 무조건 쓰이는 것은 아니고, L13에서 배울 average return MDP에서는 gamma가 0이고, episdodic task에서는 gamma가 1인 경우도 가능하다. 

Return, Not rewad

3-2. Value funtion and Bellman equation for MRP

1) State value function

V(s) : the state s에서 시작되는 return의 기댓값이다. Bellman equation을 이용하면 바로 전 상태에 있던 값과 iterative한 계산이 가능하다. 아래식을 유도할 때,   E(R_t + gamma*(R_t+1 + gamma * R_t+2...))을 유도하면 자연스럽게 아래 식처럼 유도가 된다.

이렇게 iterative 한 계산을 만들면 그 다음부터는 Dynamic programming의 한 종류인 fixed point iteration을 사용하거나, Monte-Carlo(L4), Temporal Difference Learning(L5)을 사용하면 문제가 풀릴 것이다. 혹은 계산량은 많지만 direct method로 matrix inversion을 이용할 수도 있다. 식이 linear하기 때문이다. 

Direct method : Matrix inversion

4.  Markov Decision Process (MDP)

MDP는 MRP에 decision(결정)을 결합한 것이다. Markov process는 reward values과 decisions를 같이 고려하는 것이다. Action space A만을 제외하고는 MRP와 거의 유사하다. 

 MDP components

Action space A는 현재 상태에서의 set of actions를 모은 것이다. 여기에 policy pi까지 고려하면, 

Policy PI

MDP

이런 결과가 나온다. 위에 있는 그림 MDP를 설명하자면, Markvo process처럼 state sequence가 MRP에서는 S0,R0,S1,R1,...인 state reward sequence를 만들고, 이때 p는 state transition matrix ( 현재 상태 s,action은 a일때 next state가 s'일 확률), reward R(현재 상태와 현재 action에 하면 받는 reward)이 저렇게 된다. 조금 더 엄밀히 말하면, s0,a0,r0,s1,a1,r1,...이렇게 진행되는 것이 MDP 문제이다. 

5. Value Function

Value Function 모식도

State value function

V^PI는 state value function으로 현재 상태에서 기대되는 return을 나타낸 값이고 이때 following policy 는 PI이다. 

Action value fucntion, Blank : Q-factor

Q^PI(s,a)는 action value function으로 현재 상태와 택하는 action a에서의 기대되는 return값이다. 이것 또한 policy PI를 따라간다. 저번 편에선는 V^PI끼리의 iterative equation을 구했다면 이번에는 V와 Q에 대한 식을 유도하고 이용할 것이다. 

6. Bellman Expectation Equation

그 식은 바로 벨만 기댓값 공식이다. 아래 그림처럼 간단히 유도된다. 중요한 것은 Q-factor의 기댓값이 바로 V^PI 라는 것이다. 그걸 가지고 그대로 유도하면, Q와 V에 대한 식이 유도되고, 이걸 다시 V나 Q에 대입하면, V와 Q에 대한 iterative한 결과가 나온다. 현재 상태의 기댓값으로 다음 상태가 고려된다. 즉 현재 값은 미래에 이득인 방향으로 가야한다는 의미이다. Sequential dynamic programming처럼 차례 차례 계산되는 것을 알 수 있다. 

Bellman Expectation Equation, blank: R(s,a) : 현재 state s, action a에 따른 reward이다. 

벨만은 기댓값 공식말고도 최적 공식도 만들었는데 이때 사용하는 operator는 기댓값 expectation이 아니라 최댓값 max이다. 

7. Bellman Optimality Equation

Optimal value function, 모든 state에 대해서 남들보다 값이 좋은 policy가 있다면 그 policy가 만들어내는 값들이 최적값이다. 

최적값이란 max 값을 말하며 여기서의 변수는 state s, action a가 아니라 policy이다. 물론 policy가 변함에 따라서 a, s'도 달라지겠지만, 최적의 policy에 대한 PI가 만들어내는 V^PI가 바로 V*이다. 

Bellman optimality equation

V*는 Q*(s,a) 중에서 가장 좋은 값이다. 그리고 이걸 다시 대입하면, 파란색 식처럼 나오는데, 벨만 기댓값 공식과는 다른 점이 이전 식들에는 없는 max operator가 식에 들어간 것이다. 이 max operator는 highly nonlinear한 operator로 식을 matrix inversion으로 풀 수 없게 만든다. 앞서서 V와 Q를 구할 때는 linear하게 풀렸지만, V*,Q*는 그렇게 구하지 못 한다. 

다음 편에는 3편 Dynamic programming으로 grid world 문제를 풀 것이다. 이때 Bellman expectation equation, Bellman optimality equation을 사용해서 Value Iteration, Policy Iteration을 사용하는데 이에 대해서 알아볼 것이다.