397.31 MDP의 수학적 정의와 최적 정책

1. 개요

본 절에서는 마르코프 결정 과정(Markov Decision Process, MDP)의 엄밀한 수학적 정의와 최적 정책(Optimal Policy)의 존재성 및 구조적 특성을 심층적으로 다룬다. MDP는 확률론적 환경에서의 순차적 의사 결정을 위한 수학적 프레임워크로서, Bellman의 동적 프로그래밍 원리(Principle of Optimality)에 기초한다 (Bellman, 1957). 로봇 임무 계획에서 MDP의 최적 정책은 모든 가능한 상태에 대해 기대 누적 보상을 최대화하는 행동 규칙을 제공하며, 이는 불확실한 환경에서 로봇이 최적의 임무 수행 전략을 자율적으로 결정하는 핵심 메커니즘이다.

2. MDP의 공리적 정의

2.1 기본 구성 요소

MDP는 5-튜플 \mathcal{M} = \langle \mathcal{S}, \mathcal{A}, T, R, \gamma \rangle로 공리적으로 정의된다.

정의 1 (상태 공간). \mathcal{S}는 비어 있지 않은 유한 집합으로서, 시스템이 취할 수 있는 모든 상태의 열거이다. 각 원소 s \in \mathcal{S}를 상태(State)라 한다. 상태 공간의 크기를 n = |\mathcal{S}|로 표기한다.

정의 2 (행동 공간). \mathcal{A}는 비어 있지 않은 유한 집합으로서, 에이전트가 선택할 수 있는 모든 행동의 열거이다. 상태 s에서 실행 가능한 행동의 집합을 \mathcal{A}(s) \subseteq \mathcal{A}로 표기하며, 모든 s \in \mathcal{S}에 대해 \mathcal{A}(s) \neq \emptyset이다.

정의 3 (전이 확률 함수). T: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow [0, 1]은 상태 전이의 확률적 역학을 정의하는 함수이다:

T(s, a, s') = \Pr(s_{t+1} = s' \mid s_t = s, a_t = a)

T는 다음의 확률 측도 조건을 만족하여야 한다:

\forall s \in \mathcal{S}, \; a \in \mathcal{A}(s): \quad T(s, a, s') \geq 0, \quad \sum_{s' \in \mathcal{S}} T(s, a, s') = 1

정의 4 (보상 함수). R: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}은 상태-행동 쌍에 대한 즉각적 보상을 정의하는 유계 함수이다:

|R(s, a)| \leq R_{\max} < \infty, \quad \forall s \in \mathcal{S}, \; a \in \mathcal{A}(s)

보다 일반적인 형태로 R: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R}을 사용하기도 하며, 이 경우 기대 보상은 \bar{R}(s, a) = \sum_{s'} T(s, a, s') R(s, a, s')로 계산한다.

정의 5 (할인 계수). \gamma \in [0, 1)은 미래 보상의 현재 가치를 결정하는 스칼라 상수이다. 할인 계수는 무한 수평 문제에서 총 보상의 유한성을 보장하는 역할을 한다.

2.2 마르코프 성질의 형식적 정의

MDP의 근본 가정인 마르코프 성질(Markov Property)은 다음과 같이 엄밀하게 정의된다.

정의 6 (마르코프 성질). 확률 과정 \{(s_t, a_t)\}_{t=0}^{\infty}에서, 임의의 시각 t \geq 0과 임의의 상태-행동 이력 (s_0, a_0, s_1, a_1, \ldots, s_t, a_t)에 대해 다음이 성립하면, 이 과정은 마르코프 성질을 만족한다:

\Pr(s_{t+1} = s' \mid s_0, a_0, \ldots, s_t, a_t) = \Pr(s_{t+1} = s' \mid s_t, a_t) = T(s_t, a_t, s')

이 성질은 현재 상태가 의사 결정에 필요한 모든 정보를 충분히(Sufficient) 포함하고 있음을 의미한다. 확률론적 관점에서 상태 s_t는 과거 이력에 대한 충분 통계량(Sufficient Statistic)이다.

3. 정책의 수학적 정의

3.1 정책의 분류 체계

정의 7 (정상 결정론적 정책). 정상 결정론적 정책(Stationary Deterministic Policy)은 함수 \pi: \mathcal{S} \rightarrow \mathcal{A}로 정의되며, \pi(s) \in \mathcal{A}(s)이다. 이 정책은 시간에 독립적이며 각 상태에 정확히 하나의 행동을 할당한다.

정의 8 (정상 확률론적 정책). 정상 확률론적 정책(Stationary Randomized Policy)은 조건부 확률 분포 \pi: \mathcal{S} \times \mathcal{A} \rightarrow [0, 1]로 정의되며, 다음을 만족한다:

\pi(a \mid s) \geq 0, \quad \sum_{a \in \mathcal{A}(s)} \pi(a \mid s) = 1, \quad \forall s \in \mathcal{S}

정의 9 (비정상 정책). 비정상 정책(Non-Stationary Policy)은 시간 의존적 함수 \pi_t: \mathcal{S} \rightarrow \mathcal{A}의 시퀀스 \boldsymbol{\pi} = (\pi_0, \pi_1, \pi_2, \ldots)로 정의된다. 유한 수평 MDP에서는 비정상 정책이 최적일 수 있으나, 무한 수평 할인 MDP에서는 정상 결정론적 최적 정책이 항상 존재한다.

정상 결정론적 정책의 총 수는 \prod_{s \in \mathcal{S}} |\mathcal{A}(s)|이다. 모든 상태에서 행동 집합의 크기가 m인 경우 m^n개의 정책이 존재하며, 이는 정책의 열거적 탐색이 일반적으로 비현실적임을 시사한다.

4. 가치 함수의 정의와 성질

4.1 상태 가치 함수

정의 10 (상태 가치 함수). 정책 \pi하에서 상태 s의 가치는 다음의 기대 누적 할인 보상으로 정의된다:

V^\pi(s) = \mathbb{E}_\pi \left[ \sum_{t=0}^{\infty} \gamma^t R(s_t, a_t) \;\middle|\; s_0 = s \right]

보상의 유계성과 \gamma < 1 조건에 의해 가치 함수는 반드시 유한하다:

|V^\pi(s)| \leq \sum_{t=0}^{\infty} \gamma^t R_{\max} = \frac{R_{\max}}{1 - \gamma}

따라서 V^\pi는 유계 실수 함수 공간 \mathcal{V} = \{V: \mathcal{S} \rightarrow \mathbb{R} \mid \|V\|_\infty \leq R_{\max}/(1-\gamma)\} 위의 원소이다.

4.2 행동 가치 함수

정의 11 (행동 가치 함수). 정책 \pi하에서 상태 s에서 행동 a를 선택한 후의 기대 가치는 다음과 같다:

Q^\pi(s, a) = R(s, a) + \gamma \sum_{s' \in \mathcal{S}} T(s, a, s') V^\pi(s')

상태 가치 함수와 행동 가치 함수의 관계:

V^\pi(s) = \sum_{a \in \mathcal{A}(s)} \pi(a \mid s) Q^\pi(s, a)

결정론적 정책의 경우:

V^\pi(s) = Q^\pi(s, \pi(s))

4.3 이점 함수

정의 12 (이점 함수). 이점 함수(Advantage Function)는 특정 행동의 상대적 가치를 측정한다:

A^\pi(s, a) = Q^\pi(s, a) - V^\pi(s)

이점 함수가 양수이면 행동 a가 정책 \pi의 기대 행동보다 우수함을, 음수이면 열등함을 의미한다. 최적 정책 \pi^* 하에서는 A^{\pi^*}(s, \pi^*(s)) = 0이고, 모든 차선 행동에 대해 A^{\pi^*}(s, a) \leq 0이다.

5. 벨만 방정식의 수학적 구조

5.1 벨만 기대 방정식

정책 \pi에 대한 벨만 기대 방정식(Bellman Expectation Equation)은 가치 함수의 재귀적 구조를 표현한다:

V^\pi(s) = R(s, \pi(s)) + \gamma \sum_{s' \in \mathcal{S}} T(s, \pi(s), s') V^\pi(s')

이를 벡터 형태로 표현하면:

\mathbf{V}^\pi = \mathbf{R}^\pi + \gamma \mathbf{P}^\pi \mathbf{V}^\pi

여기서 \mathbf{V}^\pi \in \mathbb{R}^n은 가치 벡터, \mathbf{R}^\pi \in \mathbb{R}^n은 보상 벡터([\mathbf{R}^\pi]_s = R(s, \pi(s))), \mathbf{P}^\pi \in \mathbb{R}^{n \times n}은 전이 행렬([\mathbf{P}^\pi]_{ss'} = T(s, \pi(s), s'))이다.

이 선형 방정식의 해는 다음과 같이 구할 수 있다:

\mathbf{V}^\pi = (\mathbf{I} - \gamma \mathbf{P}^\pi)^{-1} \mathbf{R}^\pi

\gamma < 1이므로 \gamma \mathbf{P}^\pi의 스펙트럼 반경(Spectral Radius)이 1 미만이 되어 (\mathbf{I} - \gamma \mathbf{P}^\pi)은 항상 가역(Invertible)이다. 이 직접 해법의 계산 복잡도는 O(n^3)이다.

5.2 벨만 최적 방정식

정리 1 (벨만 최적 방정식). 최적 가치 함수 V^*는 다음의 비선형 방정식 체계를 만족하는 유일한 해이다:

V^*(s) = \max_{a \in \mathcal{A}(s)} \left[ R(s, a) + \gamma \sum_{s' \in \mathcal{S}} T(s, a, s') V^*(s') \right], \quad \forall s \in \mathcal{S}

마찬가지로, 최적 행동 가치 함수 Q^*는 다음을 만족한다:

Q^*(s, a) = R(s, a) + \gamma \sum_{s' \in \mathcal{S}} T(s, a, s') \max_{a' \in \mathcal{A}(s')} Q^*(s', a'), \quad \forall s \in \mathcal{S}, \; a \in \mathcal{A}(s)

벨만 최적 방정식은 \max 연산자의 존재로 인해 비선형이므로, 직접적으로 풀 수 없으며 반복적 알고리즘이 필요하다.

5.3 벨만 연산자의 수축 사상 성질

정의 13 (벨만 최적 연산자). 벨만 최적 연산자(Bellman Optimality Operator) \mathcal{T}^*: \mathbb{R}^{|\mathcal{S}|} \rightarrow \mathbb{R}^{|\mathcal{S}|}는 다음과 같이 정의된다:

[\mathcal{T}^* V](s) = \max_{a \in \mathcal{A}(s)} \left[ R(s, a) + \gamma \sum_{s' \in \mathcal{S}} T(s, a, s') V(s') \right]

정리 2 (수축 사상 정리). 벨만 최적 연산자 \mathcal{T}^*는 최대 노름(Supremum Norm) \|\cdot\|_\infty 하에서 \gamma-수축 사상(Contraction Mapping)이다:

\|\mathcal{T}^* V_1 - \mathcal{T}^* V_2\|_\infty \leq \gamma \|V_1 - V_2\|_\infty, \quad \forall V_1, V_2 \in \mathbb{R}^{|\mathcal{S}|}

증명. 임의의 상태 s에 대해:

[\mathcal{T}^* V_1](s) - [\mathcal{T}^* V_2](s) = \max_a \left[ R(s,a) + \gamma \sum_{s'} T(s,a,s') V_1(s') \right] - \max_a \left[ R(s,a) + \gamma \sum_{s'} T(s,a,s') V_2(s') \right]

\max 연산자의 비확장성(Non-Expansiveness) 성질, 즉 |\max_a f(a) - \max_a g(a)| \leq \max_a |f(a) - g(a)|를 적용하면:

|[\mathcal{T}^* V_1](s) - [\mathcal{T}^* V_2](s)| \leq \max_a \gamma \sum_{s'} T(s,a,s') |V_1(s') - V_2(s')| \leq \gamma \|V_1 - V_2\|_\infty

따라서 \|\mathcal{T}^* V_1 - \mathcal{T}^* V_2\|_\infty \leq \gamma \|V_1 - V_2\|_\infty이 성립한다. \square

바나흐 고정점 정리(Banach Fixed-Point Theorem)에 의해, \mathcal{T}^*는 유일한 고정점 V^* = \mathcal{T}^* V^*를 가지며, 임의의 초기 가치 함수 V_0에서 출발하여 V_{k+1} = \mathcal{T}^* V_k를 반복하면 V_k \rightarrow V^*로 수렴한다. 이것이 가치 반복 알고리즘의 수렴성을 보장하는 이론적 기초이다.

6. 최적 정책의 존재성과 구조

6.1 최적 정책의 존재 정리

정리 3 (최적 정책의 존재성). 유한 상태-행동 공간을 갖는 할인 MDP \mathcal{M} = \langle \mathcal{S}, \mathcal{A}, T, R, \gamma \rangle에서, 다음을 만족하는 정상 결정론적 최적 정책 \pi^*가 반드시 존재한다:

V^{\pi^*}(s) \geq V^\pi(s), \quad \forall s \in \mathcal{S}, \; \forall \pi

증명의 핵심. 이 정리의 증명은 다음의 단계로 구성된다:

1. 벨만 최적 연산자 \mathcal{T}^*가 \gamma-수축 사상임을 보인다 (정리 2).
2. 바나흐 고정점 정리에 의해 유일한 고정점 V^*의 존재를 확인한다.
3. V^*로부터 탐욕적 정책 \pi^*(s) = \arg\max_{a} [R(s,a) + \gamma \sum_{s'} T(s,a,s') V^*(s')]를 구성한다.
4. 구성된 \pi^*가 V^{\pi^*} = V^*를 만족함을 보인다.

유한 행동 공간에서 \max 연산이 항상 달성 가능하므로(achievable), 결정론적 최적 정책이 반드시 존재한다 (Puterman, 1994).

6.2 최적 정책의 유일성과 다중성

최적 가치 함수 V^*는 유일하지만, 최적 정책 \pi^*는 유일하지 않을 수 있다. 어떤 상태 s에서 최대값을 달성하는 행동이 둘 이상 존재하면, 어느 행동을 선택하든 최적 정책이 된다:

\pi^*(s) \in \arg\max_{a \in \mathcal{A}(s)} Q^*(s, a)

\arg\max가 집합일 때, 그 원소 중 어떤 것을 선택하든 동일한 최적 가치를 보장한다.

6.3 정책 개선 정리

정리 4 (정책 개선 정리). 정책 \pi에 대해, 탐욕적 정책 \pi'를 다음과 같이 정의하면:

\pi'(s) = \arg\max_{a \in \mathcal{A}(s)} Q^\pi(s, a)

모든 상태에서 V^{\pi'}(s) \geq V^{\pi}(s)이 성립한다. 등호가 모든 상태에서 성립하면, \pi와 \pi' 모두 최적 정책이다.

증명. 임의의 상태 s에 대해:

V^\pi(s) = Q^\pi(s, \pi(s)) \leq \max_a Q^\pi(s, a) = Q^\pi(s, \pi'(s))

= R(s, \pi'(s)) + \gamma \sum_{s'} T(s, \pi'(s), s') V^\pi(s')

이 부등식을 재귀적으로 전개하면:

V^\pi(s) \leq R(s, \pi'(s)) + \gamma \sum_{s'} T(s, \pi'(s), s') V^\pi(s')

\leq R(s, \pi'(s)) + \gamma \sum_{s'} T(s, \pi'(s), s') \left[ R(s', \pi'(s')) + \gamma \sum_{s''} T(s', \pi'(s'), s'') V^\pi(s'') \right]

무한히 전개하면 V^\pi(s) \leq V^{\pi'}(s)를 얻는다. \square

이 정리는 정책 반복(Policy Iteration) 알고리즘의 수렴성을 보장한다.

7. 최적 정책의 구조적 특성

7.1 결정론적 최적 정책의 충분성

유한 MDP에서 최적 정책이 항상 결정론적으로 존재한다는 사실은 실용적으로 매우 중요하다. 이는 확률론적 정책의 무한한 공간을 탐색할 필요 없이, 유한한(m^n개의) 결정론적 정책만 고려하면 됨을 의미한다.

형식적으로, 최적 가치 함수 V^*가 주어지면 최적 정책은 단순한 \arg\max 연산으로 도출된다. 이 과정에서 확률론적 혼합은 불필요하다. 단, 제약 MDP(Constrained MDP)에서는 확률론적 최적 정책이 필요할 수 있다.

7.2 정상성(Stationarity)

무한 수평 할인 MDP에서 최적 정책은 정상적(Stationary)이다. 즉, 최적 행동은 현재 상태에만 의존하며 시간에 독립적이다:

\pi^*(s_t) = \pi^*(s), \quad \forall t \geq 0 \text{ whenever } s_t = s

이 성질은 정책을 단순한 룩업 테이블(Lookup Table)로 구현할 수 있게 하여, 로봇의 실시간 의사 결정에서 계산 비용을 크게 절감한다.

7.3 선형 프로그래밍을 통한 최적 정책 도출

MDP의 최적 가치 함수는 다음의 선형 프로그래밍(Linear Programming) 문제로도 구할 수 있다:

\min_{V} \sum_{s \in \mathcal{S}} \alpha(s) V(s)

\text{subject to} \quad V(s) \geq R(s, a) + \gamma \sum_{s'} T(s, a, s') V(s'), \quad \forall s \in \mathcal{S}, \; a \in \mathcal{A}(s)

여기서 \alpha(s) > 0은 임의의 양의 가중치이다. 이 선형 프로그래밍의 최적해는 벨만 최적 방정식의 해 V^*와 일치하며, 쌍대 변수(Dual Variable)로부터 최적 정책에 대응하는 상태-행동 점유 측도(Occupation Measure)를 도출할 수 있다 (d’Epenoux, 1963).

쌍대 문제(Dual Problem)는 다음과 같다:

\max_{\mu \geq 0} \sum_{s, a} \mu(s, a) R(s, a)

\text{subject to} \quad \sum_{a} \mu(s', a) = \alpha(s') + \gamma \sum_{s, a} \mu(s, a) T(s, a, s'), \quad \forall s' \in \mathcal{S}

여기서 \mu(s, a)는 할인된 점유 측도(Discounted Occupation Measure)이며, 최적 정책은 \pi^*(s) = \arg\max_a \mu^*(s, a)로 도출된다.

8. 계산 복잡도 분석

MDP의 최적 정책 계산에 관한 계산 복잡도는 다음과 같이 정리된다:

여기서 n = \vert\mathcal{S}\vert, m = \vert\mathcal{A}\vert이다. MDP의 최적 정책 계산은 P 클래스에 속하며, 다항 시간에 해결 가능하다. 그러나 n이 상태 변수의 수에 대해 지수적으로 증가할 수 있으므로, 실제 로봇 임무 계획에서는 상태 공간의 크기가 주요 병목이 된다.

9. 참고 문헌

• Bellman, R. (1957). Dynamic Programming. Princeton University Press.
• Puterman, M. L. (1994). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley-Interscience.
• Howard, R. A. (1960). Dynamic Programming and Markov Processes. MIT Press.
• d’Epenoux, F. (1963). “A Probabilistic Production and Inventory Problem.” Management Science, 10(1), pp. 98-108.
• Bertsekas, D. P. (2012). Dynamic Programming and Optimal Control, Vol. II, 4th edition. Athena Scientific.

본 절은 MDP의 공리적 정의, 벨만 방정식의 수학적 구조, 최적 정책의 존재성 정리 및 구조적 특성, 그리고 계산 복잡도를 다루었다. v1.0