[강화학습-2] 마르코프 결정 과정(MDP)

2. 마르코프 결정 과정(MDP)

강화학습의 모든 수학적 토대는 MDP로부터 시작됩니다.
MDP를 이해하면 가치함수·정책·벨만 방정식·탐험-활용 전략 등 이후의 거의 모든 개념이 자연스럽게 연결됩니다.

---

2-1. MDP 공식 정의

MDP는 다섯 개 요소로 이루어진 튜플입니다.

$$\langle\;\mathcal{S},\;\mathcal{A},\;P,\;R,\;\gamma\;\rangle$$

기호	이름	설명
$\mathcal{S}$	상태 집합	환경이 가질 수 있는 모든 상태 $s$
$\mathcal{A}$	행동 집합	각 상태에서 선택할 수 있는 행동 $a$
$P(s',r\mid s,a)$	전이 확률	$S_t=s,\,A_t=a$ 이후 $(S_{t+1}=s',\,R_{t+1}=r)$ 로 갈 확률
$R(s,a)$	보상 분포	$(s,a)$ 쌍에 대한 보상 기댓값 $\mathbb{E}[R_{t+1}\mid s,a]$
$\gamma\in[0,1)$	할인율	미래 보상의 현재 가치 (0 → “즉시 보상”, 1 → “장기 보상”)

마르코프 성질

$$ \Pr\!\bigl(S_{t+1}=s' \mid S_t=s,\,A_t=a,\text{과거}\bigr) =\Pr\!\bigl(S_{t+1}=s' \mid S_t=s,\,A_t=a\bigr) $$

즉 “다음 상태는 현재 상태와 행동만 알면 충분하다” 는 것이 핵심입니다.

---

2-2. 가치(Return)와 가치함수

1. 할인 누적보상 (Return)
   $$G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots$$
2. 정책 $\pi$ : $\pi(a\mid s)$ (상태마다 행동을 고르는 분포)
3. 상태가치함수
   $$V_\pi(s)=\mathbb{E}_\pi\!\bigl[G_t \mid S_t=s\bigr]$$
4. 행동가치함수
   $$Q_\pi(s,a)=\mathbb{E}_\pi\!\bigl[G_t \mid S_t=s,\,A_t=a\bigr]$$

---

2-3. 벨만 기대 방정식

현재 가치 = 즉시 보상 + 할인된 미래 가치의 기대

$$V_\pi(s)=\sum_{a}\pi(a\mid s)\sum_{s',r}P(s',r\mid s,a)\,[\,r+\gamma V_\pi(s')\,]$$

---

2-4. 벨만 최적 방정식

$$V_\*(s)=\max_{a}\sum_{s',r}P(s',r\mid s,a)\,[\,r+\gamma V_\*(s')\,]$$

이 $\max$ 연산 덕분에 정책 평가와 정책 개선이 동시에 진행됩니다.

---

2-5. 예시 MDP

(A) 3-노드 체인

[s0] --a0(+0)--> [s1] --a1(+0)--> [s2] --a2(+1)--> [terminal]
  ^                                           |
  |<-------------- a_back(+0) --------------- |

• s0 : 시작 상태
• s2 : 목표 지점, +1 보상 후 종료
• 기타 이동 보상 0, 할인율 $\gamma=0.9$
• 정책 : 앞으로 0.8, 뒤로 0.2 → 손 계산으로도 $V_\pi(s)$ 를 구해볼 수 있음.

(B) 4×4 Gridworld

S  1  2  +1
3  4  5   6
7  8  9  10
11 12 13 14

• 벽에 부딪히면 제자리
• +1 칸 도달 시 종료
• 모든 이동 보상 −0.04 → 짧은 경로 선호
• $\gamma=0.99$

---

2-6. 가치 반복 Pseudo-code

def value_iteration(states, actions, P, R, gamma=0.99, theta=1e-6):
    V = {s: 0.0 for s in states}
    while True:
        delta = 0.0
        for s in states:
            v_old = V[s]
            V[s] = max(
                sum(P[s][a][s_next] *
                    (R[s][a][s_next] + gamma * V[s_next])
                    for s_next in states)
                for a in actions
            )
            delta = max(delta, abs(v_old - V[s]))
        if delta < theta:
            break

    # 최적 정책
    pi_star = {
        s: max(
            actions,
            key=lambda a: sum(
                P[s][a][s_next] *
                (R[s][a][s_next] + gamma * V[s_next])
                for s_next in states
            )
        )
        for s in states
    }
    return V, pi_star

TIP : P[s][a][s_next], R[s][a][s_next] 테이블만 채우면 어떤 MDP라도 약 20줄 내외로 실험할 수 있습니다.

---

2-7. 할인율 $\gamma$가 1보다 작은 이유

1. 수렴 보장 : $\gamma < 1$이면 $G_t$가 기하급수적으로 감쇠하여 무한합이 유한해짐.
2. 미래 불확실성 반영 : 멀리 갈수록 보상 기대가 희미해짐.
3. 숏텀 vs 롱텀 : 실무에서 $\gamma=0.99$는 “30–50 스텝 horizon”, $\gamma=0.9$는 “10 스텝 horizon” 정도로 해석.

---

2-8. 정리 & 다음 편 예고

• MDP는 강화학습 문제를 엄밀히 기술하는 공용 언어이다.
• 벨만 방정식으로 가치함수를 재귀적으로 표현하면 계산과 학습이 가능하다.
• 작은 MDP라도 직접 코딩해보면 이후 알고리즘(정책 반복, Q-Learning, DQN)을 훨씬 쉽게 이해할 수 있다.

다음 글에서는 정적 계획법(Dynamic Programming) 으로 Gridworld MDP를 단계별로 풀어보겠습니다.
정책 평가 → 정책 개선 사이클이 어떻게 최적 전략을 찾아내는지 숫자 테이블로 직접 확인해봅시다!

---

추가 참고 자료

• Sutton & Barto, Reinforcement Learning: An Introduction, Chapter 3
• David Silver, RL Course Lecture 2 – MDP
• OpenAI Gym FrozenLake-v1 환경 소스코드