[NLP/RF] Markov Decision Process (MDP)에 대해 알아보자

앞선 포스팅에서 InstructGPT의 개념과 함께 RLHF(Reinforcement Learning Human Feedback), PPO에 대해 알아보았다.

강화 학습은 Markov Decision Process(MDP)를 해결하는 것이 목적이라고 잠깐 언급했는데, 이게 뭔지 궁금해서 더 찾아보게 되었다.

---

Markov Process (MP) = Markov Chain (MC)

Markov Decision Process(MDP)를 이해하기 전에 Markov Process(MP)에 대해 알아보도록 하자.

MP는 MDP 모델을 이해하기 위해 먼저 알아야할 중요한 

 

Markov Chain은 이산 확률 프로세스(descrete stochastic process)이다. 

stochastic process란, 확률 분포를 가진 랜덤한 변수가 일정한 시간 간격으로 값을 발생시키도록 모델링하는 것을 말한다.

이 과정은 Markov 성질인 "현재 상태가 이전 상태에만 의존하고, 과거의 상태와는 무관하다"를 기반으로 한다. 

즉, 현재 상태에서 다음 상태로의 전이 확률은 오직 현재 상태에만 의존하게 된다.

MP 모델 표현식

X: 유한한 상태 공간 (state space)의 집합

P: 전이 확률(Transition proabability), 모든 상태 X 사이의 전이 확률을 나타낸다.

 

Step

각 상태의 전이는 이산 시간 (discrete time)에 이루어지며, 상태 공간 집합 X에 속하는 어떤 임의의 상태에 머무를 때의 시간을 step이라고 한다.

(현재 step을 n이라고 하면, 다음 스텝은 n+1이 된다.)

상태 전이 확률 값을 계산하는 방법

 

: 상태 i에서 상태 j로 전이될 확률값

 

 

: step n에서 머물러 있는 상태, 즉 해당 상태에 대한 랜덤 변수를 의미

 

위 식을 통해 알 수 있는 것은 다음과 같다.

상태 i를 방문했을 때, 이전에 어떤 상태에 방문했는지에 관계 없이 상태 i에서 다음 상태 j로의 전이 확률 값은 항상 동일하다. 이를 무기억성 속성(Memoriless property)이라고도 한다. 

아까 말했던 Markov 성질인 "특정 상태의 미래 상태가 오직 현재 상태에만 의존하고, 과거 상태에는 의존하지 않는다"를 여기서 알 수 있다.

 

위 수식을 풀어서 쓰면 다음과 같다. 

 

학원에서 강의를 들은 학생이 이후에 할 수 있는 행동은 "복습을 하러 카페 가기", "PC방에 가기", "집에 가기"이다.

집에 갈 확률은 70%, 나머지에 대한 확률은 각각 10%, 20%라고 하자.

강의를 수강하고 수행할 수 있는 3가지 action은 결국 "집"에 가서 다음날 다시 "강의 수강"하러 학원에 가는 것으로 연결된다.

만약 집에서 바로 학원으로 가는 것이 아닌, 병원 또는 면접장에 들러서 학원에 간다고 생각해보자.

이런 중간 과정을 거치더라도 결론적으로 강의 수강 이후에 3가지 action을 취할 확률은 변하지 않는다.

"이전 상태가 현재 상태에 영향을 미치지 않고, 전이 확률은 항상 동일하다"라는 컨셉임을 알 수 있다.

---

Markov Reward Process (MRP)

MRP는 MP에 Reward 개념을 도입한 것이다. MP에서는 각 state별 전이 확률이 주어져 있을 뿐, 현재 state에서 다음 state로 가는 것이 얼마나 가치 있는지, 즉 어떤 점수를 가지는지는 알 수 없다.

그래서 각 state로 가는 것에 대한 가치를 정량화하기 위해 도입한 개념이 MRP이다.

 

이 state의 가치를 표현하는 함수를 Value Function이라고 하며, 특정 state에서 미래에 얻을 수 있는 모든 reward를 더한 것의 기댓값을 의미한다. 

 

 

 

위 그림에서 가장 reward 합이 높은 시퀀스는 

강의수강 -> 복습하러 카페 -> 집 -> 강의수강 -> 복습하러 카페 -> 집 이다.

 

강화 학습의 판단 기준은 reward의 합이라는 것을 기억하자.

---

Markov Decision Process (MDP)

앞서 봤던 MRP가 MP에 reward 개념을 도입한 것이라면, MDP는 MRP에 Action 개념을 추가한 컨셉이다.

 

MP, MRP에서 state가 변한다는 것은 전이 확률에 따라 임의로 변하는 것을 의미했다면, MDP는 state에서 action을 취함으로써 state가 변하는 것을 의미한다.

 

여기서 Policy의 개념이 등장한다. 

Policy (정책) 는 state에서 action을 mapping하는 함수로, 해당 state에서 어떤 action을 할 지를 결정하는 것이 policy의 역할이다.

 

생각해보면 강화 학습의 목적은 return을 최대화하는 policy를 찾는 것이다. 각  state에 도달할 때마다 return을 최대화하는 action을 취해야한다는 말이다.

 

MRP는 action이 추가되고, policy 개념이 추가되었다는 것을 알았다.

그러면 새로 추가된 action에 대한 value를 판단할 수 있게 된다.

 

1. 특정 시점 t에서 특정 state에 놓인 agent가 policy에 따라 action a를 수행한다.

2. 특정 state에서 action a를 수행하면 reward를 받게 된다.

3. 전이 확률 (transition probability)에 따라 다른 state로 전이한다.