Markov Process
강화학습(Reinforcement Learning)을 알기 위해선 MDP(Markov Decision Process를 알아야 하고, MDP를 알기 위해선 Markov Process를 알아야 한다.
Markov Chain
Markov Process 문제를 Markov Chain(MC)으로도 볼 수 있다.
간단히 말하자면 MC는 현재 상태가 과거의 모든 상태를 저장하고 있음을 나타낸다.
여기서 qt+1은 t+1 시점에 state가 q인 상태이며, P(qt+1)은 t+1시점에 state가 q일 확률이다.
위 수식을 좀 더 풀어서 쓰게 되면
qt가 t 이전 모든 시점의 정보를 저장하고 있음을 나타낸다.
State
- 과거에 대해 충분히 축적되어 있음
- 현재 state가 주어지면 과거의 state는 중요하지 않음
- 현재 state는 과거의 모든 relevant information을 축적
- 현재 state는 미래 결정에 충분히 statistic
Transition Probability
Pss'로 나타내며 이는 state s에서 state s'으로 전이할 확률을 의미한다.
Pss' = P[St+1 = s'| St = s]
→ t시점의 state가 s일 때 t+1시점의 state가 s'일 확률
Transition Matrix
from → to 상태 전이 확률
Markov Process 구성 요소
- discrete한 N개의 states S = {S1, S2, ···, SN}
- state 사이의 transition probability
- initial state π = {πi}
initial state란 state가 episode의 initial일 probability distribution이다.
ex) π ={1, 0, 0}이라면 모든 episode의 시작은 항상 s1이다.
π1(n) : n번 전이했을 때 s1의 initial state probability
π(2) = π(1) · P = π(1) · P · P = π(0) · P2
π(n) = π(0) · Pn
즉 Pn은 n-step transition probability이다.
AI-Kid