앞에서 언급했던 Stochastic 한 환경을 떠올려보자. 어떤 과정이 Stochastic 하다는 것은 그 과정이 랜덤한 값들로 이루어져 있다는 것이라고 할 수 있다. 또한, 우리는 그 값들을 발생 시간을 나타낼 수 있게 time index 를 붙일 수 있다. 이 랜덤값들의 발생 양상에 따라 두 가지로 분류할 수 있다.
Discrete-time random process
$S_1, S_2, ... S_t, S_{t+1}$ 과 같이 이산적인 시간에 랜덤값이 발생한다. 컴퓨터는 이산적인 시스템이기 때문에, 컴퓨터의 시뮬레이션은 연속적인 현상을 다룰 때 이 쪽에 가깝다.
Continuous-time random process
$\{S_t|t>= 0\}$
어떤 과정의 각 상태 $S_t$ 가 Markov Property 를 만족하면, 이는 Markov Process (Markov Chain) 이 된다. Markov Property 는 Memoryless Property 라고도 불리고, $S_{t+1}$ 의 값은 $S_t$ 값에만 영향을 받는다는 것이다. 즉, 시점 t 이전의 시점에는 영향을 받지 않는다.
$$ P(S_{t+1}=s' | S_t=s) = P(S_{t+1}=s' | S_0=s_0, S_1=s_1, ... S_t=s) $$
어떤 공의 궤적은 Markov Process 일까? 어떤 시점에서 공의 위치만으로는 다음 공의 위치를 알 수 없다. 이전의 궤적을 모르면 이동 방향을 알 수 없기 때문이다. 그러므로 Markov Process 라고 할 수 없다.
$P(S_{t+1}=s' | S_t=s)$ 는 시점의 이동에 따라 State 의 변화 확률을 나타낸다고 하여 State Transition Probability 라고 한다. Markov Process 는 State 들의 집합 S 와, State Transition Probability 행렬 P 의 tuple 쌍으로 나타낼 수 있다.
MDP 는 (S, A, P, R, $\gamma$) 의 tuple 로 정의할 수 있고, 모든 State 가 Markov Property 를 만족한다.
S: State Space
A: Action Space
P: State Transition Probability $P^a_{ss'}=p(s'|s, a)=P(S_{t+1}=s'|S_t=s,A_t=a)$
R: Reward Function $R^a_{ss'}$ → State s 에서 Action a 를 통해 State s’ 로 갈 때의 Reward
$\gamma\in[0, 1]$: Discount Factor → time step 마다 penalty 를 부과
Discount Factor 는 time step 마다 penalty 를 부과해 미래 보상의 현재 가치를 줄이는 역학을 한다.
$\gamma$=0.9 라면, 한 time step 뒤의 보상은 현재 보상의 90%만큼 가치가 있다고 간주된다.