마르코프 결정과정 (Markov Decision Process, MDP)

개요

• 에이전트는 상황이 변하는 것을 고려하여 최선의 수를 두어야 함.
• Agent의 상황 = State (현재 상태)
• 눈 앞의 보상이 아니라 미래에 얻을 수 있는 보상의 총 합을 고려해야 함. (보상의 총합을 극대화)
• 상태 $s_t$에서 행동 $a_t$를 취했을 때 얻을 수 있는 보상 $r_{t+1}$, 다음 상태 $s_{t+1}$

 

마르코프 성질

• 현재의 정보만 고려하는 성질 (어떤 상태들을 거쳐왔고, 어떤 행동들을 취해왔는지는 신경쓰지 않음.)
• MDP는 마르코프 성질을 만족한다고 가정하고 상태전이와 보상을 모델링

 

Policy

• Agent가 행동을 결정하는 방식
• 환경에 대해 필요한 정보는 모두 현재 상태에 있음. (MDP)
  • 결정적 정책 $\mu(s) = a$
  • 확률적 정책 $\pi(a|s)$

 

Agent는 정책에 따라 행동하며, 행동과 상태 전이에 따라 보상을 받고 다음 상태로 넘어감. 보상은 보상 함수가 결정.

 

Optimal Policy

수익이 최대가 되는 최적의 정책

 

Return

• $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k R_{t+k+1}$
• $\gamma$ : 감가율(Discount Factor)
• Continuous 한 경우에 무한대가 되지 않기 위함

 

State-Value Function

• 상태에 대한 기대 수익
• $V^{\pi}(s) = \mathbb{E}_{\pi}[G_t | S_t = s]$

 

• 두 정책의 우열을 가리려면 하나의 정책이 다른 정책보다 '모든 상태'에서 더 좋거나 최소한 같아야 함.
• MDP에서는 최적 정책이 적어도 하나 존재 (결정적 정책)

 

Optimal State-Value Function

 

$V^*(s) = \max_{\pi} V^{\pi}(s)$

 

 

최적의 정책 찾기 (등비급수)

V = 1
for i in range(1, 100):
	V += -1 * (0.9 ** i)
print(V)