Markov Decision Process (MDP)

 

Markov Chain

• (정의) 메모리를 갖지 않는 이산 시간 확률 과정
• Markov Process 의 두가지 조건
  1) Markov Property
  2) 이산 확률 과정
• 확률 과정 : 시간이 진행함에 따라 상태가 확률적으로 변하는 과정
• Markov Property
  현재의 state가 직전 state에만 영향을 받는다. (memoryless property)
  $$ Pr(S_{t+1}=s' | S_0, S_1, ... , S_{t-1}, S_t) = Pr(S_{t+1}=s'|S_t) $$ 

메모리를 갖지 않는다는 것은 Markov Property를 뜻합니다. 이전에 어떤 state들을 거쳐왔든 현재의 state만이 다음 state에 영향을 미친다는 것입니다. 또한, 이산 확률 과정이라 함은 시간 간격이 연속적이지 않고 이산형인 확률 과정입니다. 예를 들어서, 동전 던지기, 주사위 던지기, [1시, 2시, 3시, ...] 등이 있습니다. 연속적인 시간에 따른 측정값 같은 것은 이산 확률 과정이 될 수 없습니다. 

Markov Chain 보다 큰 범위로, Markov Property를 가지는 확률 과정을 Markov Process라고 합니다. 

• Terminal State : 다른 state로의 이동이 없는 마지막 state
• Stationary Distribution : 무한대의 시간이 지나고 나면 terminal state로 수렴하는 것 
• Transition (전이) : State들 간에 이동하는 것, 확률로 표현
• State Transition Probability Matrix : 모든 State들 간의 transition probability(전이확률)을 행렬의 형태로 정리한 것 

 

MDP (Markov Decision Process)

Markov Chain이 확률에 따라 State에서 State로 이동만 했다면, Markov Decision Process는 State에 따른 보상과 State로 이동하기 위한 행동(Action)의 개념이 추가된 것입니다.

***state 에서 action 을 함으로써 state 가 변하게 됨.

action이란 어떤 state에서 할 수 있는 행동들을 말하는데 보통 모든 state에서 가능한 행동은 모두 같습니다***

 

Reward

$$ R_t $$

$$ R_s^a\,=\,E[\,R_{t+1}\,|\,S_t=s, A_t=a\,] $$

• $ R_t $ = $S_t$에서 받는 보상 (즉각 보상)
• $ R_s^a $ = $s$에서 $a$라는 행동을 취했을 때, 다음 State에서 받을 수 있는 보상
• agent가 action을 취하면, environment가 agent에게 reward를 알려준다. 
• Markov Porcess에서는 어떤 State로 이동하는 것이 가치있는 알 수 없었다. 
  어떤 State로 가면 보상을 받도록 하여 방향을 설정하기 위한 개념
• 바둑에서는 승패, 아타리게임에서는 score가 Reward이다. 
• 강화학습에서는 정답이나 사전에 환경에 대한 지식 없이 Reward를 통해서 agent가 학습하게 된다. 

 

Return 

$$G_t \,=\,R_{t+1}+\gamma R_{t+2}+... \,=\, \sum_{k=0}^\infty \gamma^k R_{t+k+1}$$

• 즉각 보상 뿐만 아니라, 미래의 보상들까지 현재 가치로 환산한 합
• $\gamma$ ($0<\gamma <1$)
  Discount factor, 미래에 받을 보상의 가치는 현재 받는 보상의 가치보다 적기 때문에 미래가치를 현재가치로 환산해주는 역할

 

State-value function

$$ V(s) \,=\, E[\,G_t\, |\, S_t=s\,]$$ 

$$ V_{\pi}(s) \,=\, E_{\pi}[\,G_t\, |\, S_t=s\,]$$ 

• 상태 $s$의 가치
• State $s$의 가치는 $s$에서 미래에 얻을 수 있는 Return의 기댓값으로 평가됨
• 이동가능한 모든 시나리오의 Return 값의 기댓값
• agent 는 다음으로 갈 수 있는 state들의 가치를 보고 높은 가치의 state로 이동
  => 다음으로 갈 state-value 를 효율적이면서 정확하게 구하는 것이 매우 중요

 

Action-value function

$$ q_{\pi}(s,a) \,=\, E_{\pi}[\,G_t\, |\, S_t=s, \, A_t=a]$$ 

• 행동 $a$의 가치
• 상태 $s$에서 행동$a$를 취했을 때, 기대되는 Return의 값으로 평가됨.
• State-value function 에는 사실 그 state에서 어떤 action을 했는지에 따라 달라지는 return에 대한 정보도 포함되어 있다. 
• agent 입장에서는 취할 수 있는 모든 행동으로 가능한 다음 state들을 모두 찾고,
  그 state들의 state-value를 구한뒤, state-value가 높은 state로 가기위해 어떤 action을 취해야 할지 선택해야 한다. 
  따라서, 최종적으로는 action-value를 구할 수 있어야 한다. 
• 어떤 행동을 했을 때 얼마나 좋을 것인가? 
• 다른 말로 Q-value
• q-learning이나 DQN(deep q-network)같은 곳에서 사용되는 q도 action-value function이다. 

 

Policy

$$ \pi(a\,|\,s)\,=\, P(\,A_t=a\,|\,S_t=s\,)$$

• 해당 state에서 어떤 action을 할 지
• (정의) state s에서 aciton a를 할 확률
• $V(S_t)$ 를 최대화 하는 정책을 Optimal Policy 라고 한다.
• 결국에 강화학습의 목적은 Optimal Policy ( accumulative Reward = Return 을 최대화하는 Policy)를 찾는 것

 

---

Reference

https://sumniya.tistory.com/3

[Ch.2] Markov Decision Process

 

https://dnddnjs.gitbooks.io/rl/content/mdp.html

MDP · Fundamental of Reinforcement Learning