Markov Decision Process

강화학습은 MDP의 문제를 푸는 것

https://sumniya.tistory.com/3 참조

Markov Process의 정의

• 확률론에서 Markov Process는 메모리를 갖지 않는 이산 시간 확률 과정
• 확률 과정: 시간이 진행함에 따라 상태가 확률적으로 변화하는 과정
• 확률 분포를 따르는 random variable 가 discrete한 time interval 마다 값을 생성해내는 것을 의미
• time interval이 discrete하고 현재의 state가 이전 state에만 영향을 받는 확률 과정을 Markov Process라 함

Markov Property

• 어떤 시간에 특정 state를 도달하든 그  이전에 어떤 state를 거쳐왔든 다음 state로 갈 확률은 항상 같다
• $Pr(S_{t+1} = s' | S_0, S_1, \cdots, S_{t-1}, S_t) = Pr(S_{t+1} = s' | S_t)$
• 0 ~ t시간 까지의 여러 state를 거쳐오고 (t+1) 시간에 s'라는 state에 도달할 활귤이 바로 직전 t시간의 state에서 state $s'$로 올 확률은 같다.

State Transition Probability Matrix

• State들 간에 이동하는 것을 transition이라 하며 이를 확률로 표현
• state transition probability: $P_{ss'} = Pr(S_{t+1} = s' | S_t = s)$

---

Markov Reward Process(MRP)

Markov reward process of student

• Markov Process에 Reward의 개념을 추가한 것
• 현재 state에서 다음 state로 가는 것이 얼마나 가치있는지 알기 위하여 도입한 Reward의 개념
• $R_s = E[r_{t+1} | S_t = s]$: state를 받아 reward의 기대값으로 mapping하는 함수
• 바로 다음 시간인 (t+1)에 얻을 수 있는 보상이기 때문에 immediate reward라 함

Discounting Factor

• 현재의 state의 정확한 가치를 구하기 위해서 어느 시점에서 reward를 얻는 시점이 중요
• discounting factor $\gamma$ 는 [0, 1]의 값으로 미래가치를 현재 시점에서의 가치로 변환

Return

• 먼 미래에 얻을 수 있는 total reward에 대해 고려하게 되고 이를 Return이라 함 $$G_t = R_{t+1} + \gamma R_{t+2} + \cdots = \sum_{k=0} ^\infty \gamma^k R_{t+k+1}$$
• $R$: immediate reward로서 현재가치로 환산하여 합한 것

Value Function of MRP

• state의 가치를 표현하는 함수를 Value Function
• 어떠한 state에서 미래를 얻을 수 있는 모든 reward를 더한 것의 expectation $$V(s) =  E[G_t | S_t = s]$$
• state s 에서 이동 가능한 state들의 scenario들을 따라 그 state들의 reward에 discounting factor를 적용하여 모두 더한 값이 state s에서의 가치 $V(s)$.

---

Markov Decision Process(MDP)

MP + reward = MRP, MRP + action = MDP

Action

• state에서 action을 하여 state가 변함

Policy

• state에서 action을 mapping하는 함수
• 해당 state에서 어떤 action을 할 지를 정하는 것을 policy라 함 $$\pi (a | s) = Pr(A_t = a | S_t = s)$$

Value Function of MDP

• MDP의 process
  • t시점에 state s에 놓인 agent가 policy에 따라 action a 수행
  • state s에서 action a를 수행하면 reward를 받음
  • transition probability에 따라 state s'로 전이
• State-Value Function
  • state에서 선택하는 policy에 따라 그 action이 달라지고 이후 state가 달라지기 때문에 policy에 영향을 받음 $$V_\pi (s) = E_\pi [G_t | S_t = s]$$
  • MDP에서 state s의 가치는 해당 state에서 policy에 얻게 되는 reward들의 총합(return)을 나타냄
• Action-Value Function
  • agent가 하는 action에 대하여 value를 판단 $$q_\pi (s, a) = E_\pi [G_t | S_t = s, A_t = a]$$
  • action a의 가치는 State s 에서 policy에 따라 action을 취했을 때, 얻게 되는 reward들의 총합을 나타냄