Day 56: 마르코프 결정 과정 (Markov Decision Processes, MDPs)

학습 목표

강화 학습 문제를 수학적으로 모델링하기 위한 프레임워크입니다.
순차적 의사 결정 문제를 다루며, 현재 상태가 주어지면 과거의 상태와 무관하게 미래의 상태 전이가 결정되는 마르코프 속성(Markov Property)을 가정합니다.
MDP는 다음의 튜플로 정의됩니다: (S, A, P, R, γ)
- S (States): 가능한 모든 상태의 유한 집합. (어제 학습한 내용)
- A (Actions): 가능한 모든 행동의 유한 집합. (어제 학습한 내용)
- P (Transition Probability Function, P(s’|s, a)): 상태 s에서 행동 a를 취했을 때 다음 상태 s’로 전이될 확률. P(s’|s, a) = P[S_{t+1} = s’ | S_t = s, A_t = a]
- R (Reward Function, R(s, a, s’)): 상태 s에서 행동 a를 취하여 상태 s’로 전이했을 때 받는 즉각적인 보상. 때로는 R(s, a) 또는 R(s)로 단순화하여 표현하기도 합니다.
- γ (Discount Factor, 감가율): 0과 1 사이의 값으로, 미래 보상의 현재 가치를 나타냅니다. γ가 0에 가까우면 단기적인 보상에 집중하고, 1에 가까우면 장기적인 보상까지 고려합니다.

“미래는 과거와 독립적으로 현재에만 의존한다.”
특정 시점 t+1에서의 상태 S_{t+1}과 보상 R_{t+1}은, 바로 이전 시점 t에서의 상태 S_t와 행동 A_t에만 의존하고, 그 이전의 모든 상태와 행동 이력과는 무관하다는 성질입니다.
P[S_{t+1} | S_t, A_t, S_{t-1}, A_{t-1}, …, S_0, A_0] = P[S_{t+1} | S_t, A_t]

정책 π를 따랐을 때 각 상태 또는 상태-행동 쌍이 얼마나 좋은지를 나타내는 함수입니다.
- 상태 가치 함수 (State-Value Function, V^π(s)): 상태 s에서 시작하여 정책 π를 따랐을 때 얻을 수 있는 총 감가된 보상의 기댓값. V^π(s) = E_π[G_t | S_t = s] = E_π[∑_k=0^∞ γ^kR_t+k+1 | S_t = s]
- 행동 가치 함수 (Action-Value Function, Q^π(s, a)): 상태 s에서 행동 a를 취하고 이후 정책 π를 따랐을 때 얻을 수 있는 총 감가된 보상의 기댓값. Q^π(s, a) = E_π[G_t | S_t = s, A_t = a] = E_π[∑_k=0^∞ γ^kR_t+k+1 | S_t = s, A_t = a]

가치 함수들 사이의 관계를 나타내는 방정식으로, 현재 상태의 가치와 다음 상태의 가치 사이의 관계를 재귀적으로 표현합니다.
강화 학습 알고리즘의 핵심적인 기반이 됩니다.
- 벨만 기대 방정식 (Bellman Expectation Equation) for V^π: V^π(s) = ∑_a π(a|s) ∑_s’ P(s’|s, a) [R(s, a, s’) + γV^π(s’)]
- 벨만 기대 방정식 (Bellman Expectation Equation) for Q^π: Q^π(s, a) = ∑_s’ P(s’|s, a) [R(s, a, s’) + γ∑_a’ π(a’|s’)Q^π(s’, a’)]
벨만 최적 방정식 (Bellman Optimality Equation): 최적 가치 함수 V*(s)와 Q*(s,a)에 대한 방정식.
- V*(s) = max_a ∑_s’ P(s’|s, a) [R(s, a, s’) + γV*(s’)]
- Q*(s, a) = ∑_s’ P(s’|s, a) [R(s, a, s’) + γmax_a’Q*(s’, a’)]