마르코프 결정 과정

1. 개요[편집]

마르코프 결정 과정 Markov Decision Process (MDP)
구성	(S, A, P, R, γ) 다섯 쌍
핵심 가정	마르코프 성질 — 현재 상태가 과거를 전부 요약
목적함수	할인 누적 보상의 기대값
해	결정론적 정상 정책 π*(s)
푸는 법	동적 계획법 / 강화 학습

“지금 어디에 서 있는지만 말해줘. 어떻게 여기까지 왔는지는 안 물어볼게.”

마르코프 결정 과정(Markov Decision Process, MDP)은 불확실한 환경에서 순차적으로 의사결정을 내리는 문제를 형식화한 수학적 모형이다. 상태가 확률적으로 바뀌고, 행동이 그 확률에 영향을 주며, 매 순간 스칼라 보상이 들어오는 상황 — 로봇 제어, 재고 관리, 게임 AI, 유지보수 스케줄링이 전부 이 틀 하나에 들어간다.

여기서 짚고 갈 것은 MDP는 알고리즘이 아니라 문제 그 자체라는 점이다. 이 문서는 “무엇을 푸는가”만 다룬다. 그 문제를 실제로 푸는 알고리즘(가치 반복·정책 반복)은 동적 계획법에, 전이 확률을 모른 채 표본으로 때려 맞히는 방법론은 강화 학습에 있다. 순서를 헷갈리면 안 된다. 모형을 먼저 세우고, 그다음에 푼다. 모형이 틀렸으면 아무리 좋은 솔버를 붙여도 검증 및 확인에서 얌전히 터진다.

2. 다섯 쌍 (S, A, P, R, γ)[편집]

MDP는 다섯 개의 물건으로 완전히 정의된다.

• 상태 공간 $\mathcal{S}$ — 세계의 현황을 담는 집합. 격자 칸 번호일 수도, 로봇의 관절 각도·각속도 벡터일 수도 있다.
• 행동 공간 $\mathcal{A}$ — 각 상태에서 고를 수 있는 행동. 상태에 따라 다르면 $\mathcal{A}(s)$로 쓴다.
• 전이 확률 $P(s' \mid s, a)$ — 상태 $s$에서 행동 $a$를 했을 때 $s'$로 갈 확률. 모든 $s'$에 대해 합이 1이다. 이것이 곧 환경 모형이다.
• 보상 함수 $R(s, a)$ (또는 $R(s,a,s')$) — 그 전이로 받는 즉시 보상. 설계자가 정하는 값이고, 여기가 대부분의 사고가 나는 지점이다.¹
• 할인율 $\gamma \in [0, 1)$ — 미래 보상을 얼마나 깎아서 볼 것인가.

목표는 할인 누적 보상(return)의 기대값을 최대화하는 것이다.

$$G_t = \sum_{k=0}^{\infty} \gamma^{k}\, r_{t+k+1}, \qquad \max_{\pi}\ \mathbb{E}_{\pi}\!\left[G_0\right]$$

2.1. 마르코프 성질[편집]

이름값을 하는 가정은 이것 하나다.

$$\Pr(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \dots, s_0) = \Pr(s_{t+1} \mid s_t, a_t)$$

현재 상태가 미래를 예측하는 데 필요한 과거 정보를 전부 요약하고 있다는 뜻이다. 물리 시뮬레이션 하는 사람에게는 익숙한 이야기 — 해밀토니안 역학에서 위상공간 좌표 $(q, p)$만 알면 궤적 전체가 결정되는 것과 같은 구조다. 다만 여기서는 결정론이 아니라 확률 전이라는 점만 다르다.

주의할 것은 마르코프 성질이 자연법칙이 아니라 상태 변수를 어떻게 잡았느냐의 문제라는 사실이다. 위치만 상태로 두면 공의 미래를 못 맞히지만 (위치, 속도)를 상태로 두면 맞힌다. “이 문제는 마르코프가 아니다”라는 말은 보통 “상태를 덜 잡았다”의 다른 표현이다. 상태를 충분히 키우면 대부분 마르코프가 되지만, 그 대가로 상태 공간이 폭발한다. 세상에 공짜는 없다.

3. 정책과 가치함수[편집]

정책 $\pi$는 상태를 행동으로 보내는 규칙이다. 확률적 정책은 $\pi(a \mid s)$, 결정론적 정책은 $\pi(s) = a$로 쓴다. 정책이 정해지면 MDP는 그냥 마르코프 연쇄(Markov chain)로 축소되고, 각 상태의 “가치”를 물을 수 있게 된다.

$$V^{\pi}(s) = \mathbb{E}_{\pi}\!\left[\sum_{k=0}^{\infty} \gamma^{k} r_{t+k+1} \,\middle|\, s_t = s\right]$$ $$Q^{\pi}(s, a) = \mathbb{E}_{\pi}\!\left[\sum_{k=0}^{\infty} \gamma^{k} r_{t+k+1} \,\middle|\, s_t = s,\ a_t = a\right]$$

$V^\pi$는 상태 가치, $Q^\pi$는 행동 가치다. 둘의 차이는 “첫 수를 정책에 맡기느냐, 내가 지정하느냐”뿐이고 $V^\pi(s) = \sum_a \pi(a|s) Q^\pi(s,a)$로 이어져 있다. 실무에서 $Q$가 사랑받는 이유는 명백하다 — $Q$만 있으면 전이 확률 $P$를 몰라도 $\arg\max_a Q(s,a)$로 행동을 뽑을 수 있지만, $V$만 있으면 한 스텝 앞을 내다보기 위해 $P$가 필요하다.

4. 벨만 방정식과 최적 정책[편집]

가치함수는 자기 자신에 대한 재귀식을 만족한다. 이것이 벨만 기대 방정식이다.

$$V^{\pi}(s) = \sum_{a} \pi(a \mid s) \sum_{s'} P(s' \mid s, a)\left[\, R(s,a) + \gamma\, V^{\pi}(s') \,\right]$$

최적 정책에 대해서는 기대값 자리에 최댓값이 들어와 벨만 최적 방정식이 된다.

$$V^{*}(s) = \max_{a} \sum_{s'} P(s' \mid s, a)\left[\, R(s,a) + \gamma\, V^{*}(s') \,\right]$$

이 방정식은 그냥 예쁜 항등식이 아니라 정리를 하나 품고 있다. 유한 상태·유한 행동이고 $\gamma < 1$이면, 위 방정식의 해 $V^*$는 유일하게 존재하고, 그로부터 얻는 탐욕 정책 $\pi^*(s) = \arg\max_a Q^*(s,a)$는 모든 상태에서 동시에 최적이다.² 게다가 그 최적 정책은 **결정론적이고 정상(stationary)**이어도 충분하다 — 주사위를 섞을 필요도, 시각 $t$를 볼 필요도 없다. 상대가 있는 게임 이론에서 혼합 전략이 필수인 것과 대비되는 지점이다. MDP의 “상대”는 그냥 무심한 확률일 뿐, 내 전략을 읽고 대응하지 않기 때문이다.

5. 할인율과 유효 지평선[편집]

$\gamma$는 수학적으로는 무한 급수를 수렴시키는 장치다. 보상이 $|r| \le R_{\max}$로 유계면

$$|V^{\pi}(s)| \le \frac{R_{\max}}{1 - \gamma}$$

로 가치가 유계가 되고, 이 유계성이 이후 모든 수렴 증명의 밑돌이 된다. 공학적으로는 시상수로 읽는 것이 훨씬 유용하다. $\gamma^k$가 $1/e$로 떨어지는 시점이 대략

$$k_{\text{eff}} \approx \frac{1}{1 - \gamma}$$

스텝이므로, $\gamma = 0.9$는 약 10스텝, $\gamma = 0.99$는 약 100스텝 앞까지 신경 쓰는 에이전트다. 제어 주기가 1 kHz인 시스템에 $\gamma=0.9$를 쓰면 10 ms 앞만 보는 근시안이 된다는 뜻. $\gamma$는 하이퍼파라미터가 아니라 물리적 시간 스케일이다.³ 목표까지 200스텝 걸리는 문제에 $\gamma=0.9$를 꽂고 “학습이 안 돼요”라고 하는 것은, CFL 조건을 어겨놓고 솔버 탓을 하는 것과 같은 종류의 실수다.

6. 축소판과 확장[편집]

다중 슬롯머신(multi-armed bandit) 문제는 상태가 하나뿐인 MDP다. $|\mathcal{S}| = 1$이면 전이 확률은 자명해지고($P(s|s,a)=1$), 남는 것은 “어느 행동의 기대 보상이 가장 큰가”뿐이다. 그래서 밴딧에서는 탐험 대 이용만 순수하게 남고, 신용 할당 문제는 사라진다. 위 시뮬레이션의 UCB1은 몬테카를로 트리 탐색의 UCT 선택 규칙과 같은 물건이기도 하다.

반대 방향으로 확장하면 이렇게 된다.

• POMDP(부분관측 MDP) — 상태를 직접 못 보고 관측 $o$만 받는다. 이때는 상태 위의 확률분포(belief state)를 새로운 상태로 삼아야 하고, 그 순간 상태 공간이 연속·무한 차원이 된다. 그래서 POMDP는 일반적으로 계산 불가능(undecidable) 영역으로 넘어간다. 실무에서는 칼만 필터나 입자 필터로 belief를 근사한 뒤 그 위에서 MDP인 척한다.
• 연속 상태·행동 공간 — 표로 $V$를 저장할 수 없으니 함수 근사가 필요하다. 선형 기저, 가우시안 프로세스, 심층 학습 신경망이 모두 여기에 쓰인다.
• 평균 보상 기준 — $\gamma \to 1$인 무한 지평선 문제에서는 할인 합이 발산하므로, 대신 단위 시간당 평균 보상 $\rho^\pi = \lim_{T\to\infty} \frac{1}{T}\mathbb{E}[\sum_{t<T} r_t]$을 최대화한다. 화학 플랜트 정상운전처럼 “언제 끝난다”가 없는 문제의 정직한 정식화다.

7. 모형을 아느냐 모르느냐[편집]

MDP를 세운 다음 갈림길은 하나다. $P$와 $R$을 아느냐.

상황	접근	대표 방법
$P, R$을 안다	모형 기반 (planning)	가치 반복, 정책 반복, 선형계획법 정식화
모른다, 표본만 있다	모형 프리 (learning)	Q러닝, SARSA, 정책경사
모르지만 배워서 쓴다	모형 학습 후 계획	Dyna, MBPO, 대리 모델 기반 계획

시뮬레이션 판에서 재미있는 것은 세 번째 열이 사실상 우리 밥그릇이라는 점이다. 물리 엔진이나 CFD 솔버가 곧 $P$의 구현체이기 때문이다. 시뮬레이터가 있으면 모형 프리 알고리즘도 사실상 모형 기반처럼 쓸 수 있다 — 리셋하고 다시 굴리면 되니까. 반대로 시뮬레이터와 현실의 간극(sim-to-real gap)은 곧 “내 $P$가 틀렸다”는 말이고, 이건 불확실성 정량화가 늘 하던 이야기의 강화학습판 번역일 뿐이다.⁴

8. 관련 문서[편집]

• 동적 계획법 — 이 문제를 실제로 푸는 알고리즘
• 강화 학습 — $P$를 모를 때의 표본 기반 해법
• 몬테카를로 트리 탐색 · 미니맥스 알고리즘
• 칼만 필터 · 입자 필터 — belief 추정
• 게임 이론 · 유틸리티 AI · 행동 트리
• 몬테카를로 방법 · 통계
• 해밀토니안 역학 — 결정론적 마르코프 구조의 물리판

9. Footnotes[편집]

1. 보상 설계(reward shaping)는 MDP에서 가장 인간적인 부분이자 가장 자주 터지는 부분이다. “빨리 가라”고 시간당 −1을 줬더니 절벽에서 뛰어내려 에피소드를 조기 종료시키는 에이전트가 나오는 것이 국룰. 이걸 보상 해킹(reward hacking)이라고 부르는데, 사실 에이전트는 시킨 대로 완벽하게 최적화한 것이고 틀린 건 설계자다. ↩

2. “모든 상태에서 동시에” 부분이 은근히 강한 주장이다. 일반적인 다목적 최적화라면 한 목적을 올리면 다른 목적이 내려가는 파레토 트레이드오프가 나오는데(다중기준 방법 참고), MDP에서는 그런 일이 없다. 벨만 최적 방정식의 해가 모든 상태를 동시에 지배하기 때문이다. ↩

3. $\gamma$를 0.99에서 0.999로 올리는 것은 “조금 더 멀리 본다”가 아니라 유효 지평선을 100에서 1000으로 10배 늘리는 조작이다. 로그 스케일로 생각해야 하는 파라미터인데 UI에서는 대개 0~1 슬라이더로 놓여 있어서, 초심자가 0.9와 0.99 사이의 심연을 못 보고 지나간다. ↩

4. 그래서 요즘은 시뮬레이터 파라미터(마찰계수, 질량, 지연시간)를 일부러 무작위로 흔들어 학습시키는 도메인 무작위화(domain randomization)를 쓴다. 정체를 밝히자면 이것은 실험계획법과 강건 설계를 강화학습 어휘로 재포장한 것에 가깝다. ↩