8.54 마르코프 결정 과정(MDP)의 기초

1. 마르코프 결정 과정의 정의

마르코프 결정 과정(Markov Decision Process, MDP)은 순차적 의사결정 문제의 수학적 프레임워크로, 마르코프 성질을 만족하는 상태 전이에 행동(action)과 보상(reward)을 추가한 모델이다. 강화 학습과 최적 제어의 이론적 기반을 형성한다.

2. MDP의 구성 요소

MDP는 다섯 요소의 튜플 $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$ 로 기술된다.

2.1 상태 공간 $\mathcal{S}$

시스템이 취할 수 있는 모든 상태의 집합이다. 유한( $\lvert\mathcal{S}\rvert < \infty$ ) 또는 무한(연속) 상태 공간이 가능하다.

2.2 행동 공간 $\mathcal{A}$

각 상태에서 에이전트가 선택할 수 있는 행동의 집합이다. 상태에 따라 가능한 행동이 제한될 수 있다( $\mathcal{A}(s)$ ).

2.3 전이 확률 $P(s' \vert s, a)$

상태 $s$ 에서 행동 $a$ 를 수행했을 때 다음 상태 $s'$ 로 전이할 확률이다. 마르코프 성질에 의해:

$P(s_{t+1} \vert s_t, a_t, s_{t-1}, a_{t-1}, \ldots) = P(s_{t+1} \vert s_t, a_t)$

2.4 보상 함수 $R(s, a, s')$ 또는 $R(s, a)$

상태 $s$ 에서 행동 $a$ 를 수행하여 상태 $s'$ 로 전이했을 때 받는 즉각적 보상이다. 단순화를 위해 $R(s, a) = \mathbb{E}[R(s, a, s') \vert s, a]$ 로 기댓값을 사용하기도 한다.

2.5 할인 인자 $\gamma \in [0, 1)$

미래 보상의 현재 가치를 할인하는 계수이다. $\gamma$ 가 작으면 근시안적(myopic), 크면 장기적 보상을 중시한다. $\gamma < 1$ 은 무한 지평(infinite horizon) 문제에서 누적 보상의 유한성을 보장한다.

3. 정책(Policy)

정책 $\pi$ 는 상태에서 행동으로의 사상이다.

결정론적 정책: $\pi: \mathcal{S} \to \mathcal{A}$
확률적 정책: $\pi(a \vert s) = P(a_t = a \vert s_t = s)$

정책은 에이전트의 행동 전략을 기술하며, MDP의 최적화 대상이다.

4. 누적 보상과 목표

4.1 할인 누적 보상(Return)

시각 $t$ 부터의 할인 누적 보상:

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

4.2 MDP의 목표

$\max_\pi \mathbb{E}^\pi[G_0] = \max_\pi \mathbb{E}^\pi\left[\sum_{t=0}^{\infty}\gamma^t R_{t+1}\right]$

기대 누적 보상을 최대화하는 정책 $\pi^*$ 를 찾는 것이다.

5. 가치 함수(Value Function)

5.1 상태 가치 함수

정책 $\pi$ 하에서 상태 $s$ 의 가치는 $s$ 에서 시작하여 $\pi$ 를 따랐을 때의 기대 누적 보상이다.

$V^\pi(s) = \mathbb{E}^\pi[G_t \vert s_t = s]$

5.2 행동 가치 함수(Q-함수)

상태 $s$ 에서 행동 $a$ 를 수행한 후 $\pi$ 를 따랐을 때의 기대 누적 보상이다.

$Q^\pi(s, a) = \mathbb{E}^\pi[G_t \vert s_t = s, a_t = a]$

5.3 관계

$V^\pi(s) = \sum_{a}\pi(a \vert s)Q^\pi(s, a)$

6. 벨만 방정식(Bellman Equation)

6.1 기대 벨만 방정식

가치 함수는 재귀적 구조를 갖는다.

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

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

6.2 최적 벨만 방정식

최적 가치 함수 $V^* = \max_\pi V^\pi$ 와 $Q^* = \max_\pi Q^\pi$ 는 벨만 최적 방정식을 만족한다.

$V^*(s) = \max_a\sum_{s'}P(s' \vert s, a)[R(s, a, s') + \gamma V^*(s')]$

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

7. 최적 정책

최적 가치 함수로부터 최적 정책을 도출한다.

$\pi^*(s) = \arg\max_a Q^*(s, a) = \arg\max_a\sum_{s'}P(s' \vert s, a)[R(s, a, s') + \gamma V^*(s')]$

모든 MDP는 결정론적 최적 정책을 갖는다.

8. MDP 해법 알고리즘

8.1 가치 반복(Value Iteration)

$V_{k+1}(s) = \max_a\sum_{s'}P(s' \vert s, a)[R(s, a, s') + \gamma V_k(s')]$

8.2 정책 반복(Policy Iteration)

정책 평가와 정책 개선을 교대로 수행한다.

8.3 선형 계획법

작은 MDP는 선형 계획 문제로 정식화하여 풀 수 있다.

9. 로봇 공학에서의 MDP

경로 계획: 이산 격자 위의 최적 경로 계획이 MDP로 정식화된다. 상태는 격자 셀, 행동은 이동 방향, 보상은 목표 도달 여부와 경로 비용이다.

로봇 행동 계획: 작업 계획의 고수준 행동 결정(어느 위치로 이동, 어떤 도구를 사용 등)이 MDP로 모델링된다.

강화 학습의 기반: 강화 학습의 모든 알고리즘(Q-학습, SARSA, 정책 경사법 등)이 MDP 프레임워크에서 정식화된다.

10. 참고 문헌

Puterman, M. L. (2014). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley.
Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press.
Bertsekas, D. P. (2012). Dynamic Programming and Optimal Control (Vol. 1, 4th ed.). Athena Scientific.
Thrun, S., Burgard, W., & Fox, D. (2005). Probabilistic Robotics. MIT Press.

version: 1.0