397.35 POMDP의 수학적 정의와 신뢰 상태(Belief State)

1. 개요

본 절에서는 부분 관측 마르코프 결정 과정(POMDP)의 엄밀한 수학적 정의와 신뢰 상태(Belief State)의 이론적 기초를 심층적으로 다룬다. POMDP는 에이전트가 환경의 실제 상태를 직접 관측할 수 없는 상황에서의 확률론적 순차 의사 결정을 형식화하는 프레임워크이다. 신뢰 상태는 에이전트의 행동-관측 이력에 기반한 상태 추정을 확률 분포로 표현하며, POMDP를 연속 상태 공간의 완전 관측 MDP(Belief MDP)로 변환하는 핵심 개념이다. 이 변환은 Åström에 의해 최초로 제안되었으며 (Åström, 1965), Smallwood와 Sondik에 의해 POMDP의 가치 함수가 신뢰 상태의 볼록 구분선형(Piecewise Linear and Convex, PWLC) 함수임이 증명되었다 (Smallwood & Sondik, 1973).

2. POMDP의 공리적 정의

2.1 기본 구성 요소

정의 1 (POMDP). 부분 관측 마르코프 결정 과정은 7-튜플 $\mathcal{P} = \langle \mathcal{S}, \mathcal{A}, T, R, \Omega, O, \gamma \rangle$ 로 정의된다.

(i) 상태 공간(State Space). $\mathcal{S} = \{s_1, s_2, \ldots, s_n\}$ 은 환경의 모든 가능한 상태를 열거하는 비어 있지 않은 유한 집합이다. 상태 $s \in \mathcal{S}$ 는 에이전트에게 직접 관측 가능하지 않다. 이것이 완전 관측 MDP와의 근본적 차이이다.

(ii) 행동 공간(Action Space). $\mathcal{A} = \{a_1, a_2, \ldots, a_m\}$ 은 에이전트가 선택할 수 있는 행동의 유한 집합이다. 상태 의존적 행동 집합 $\mathcal{A}(s)$ 를 정의할 수 있으나, 에이전트가 상태를 모르므로 일반적으로 $\mathcal{A}(s) = \mathcal{A}$ 로 설정한다.

(iii) 전이 함수(Transition Function). $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(s, a, s') \geq 0, \quad \sum_{s' \in \mathcal{S}} T(s, a, s') = 1, \quad \forall s \in \mathcal{S}, \; a \in \mathcal{A}$

(iv) 보상 함수(Reward Function). $R: \mathcal{S} \times \mathcal{A} \rightarrow \mathbb{R}$ 은 유계 함수로서 $|R(s, a)| \leq R_{\max}$ 이다. 보다 일반적인 형태 $R: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R}$ 도 사용된다.

(v) 관측 공간(Observation Space). $\Omega = \{o_1, o_2, \ldots, o_p\}$ 은 에이전트가 수신할 수 있는 관측(Observation)의 유한 집합이다. 관측은 센서 판독값, 환경 신호, 통신 메시지 등 에이전트가 환경으로부터 수신하는 모든 정보를 추상화한다.

(vi) 관측 함수(Observation Function). $O: \mathcal{S} \times \mathcal{A} \times \Omega \rightarrow [0, 1]$ 은 관측의 조건부 확률을 정의한다:

$O(s', a, o) = \Pr(o_{t+1} = o \mid s_{t+1} = s', a_t = a)$

다음의 정규화 조건을 만족한다:

$O(s', a, o) \geq 0, \quad \sum_{o \in \Omega} O(s', a, o) = 1, \quad \forall s' \in \mathcal{S}, \; a \in \mathcal{A}$

관측 함수는 센서 모델(Sensor Model)을 수학적으로 표현한 것이다. 관측이 상태를 정확히 반영하는 경우( $O(s', a, o) = \mathbf{1}[o = s']$ ) POMDP는 MDP로 퇴화한다.

(vii) 할인 계수(Discount Factor). $\gamma \in [0, 1)$ 은 미래 보상의 할인율을 결정하는 스칼라 상수이다.

2.2 행렬 표현

POMDP의 전이 역학과 관측 역학은 행렬 형태로 표현할 수 있다. 행동 $a$ 에 대한 전이 행렬 $\mathbf{T}_a \in \mathbb{R}^{n \times n}$ 와 관측 행렬 $\mathbf{O}_a \in \mathbb{R}^{n \times p}$ 를 정의한다:

$[\mathbf{T}_a]_{ij} = T(s_i, a, s_j), \quad [\mathbf{O}_a]_{jk} = O(s_j, a, o_k)$

전이 행렬의 각 행은 확률 벡터이므로 $\mathbf{T}_a \mathbf{1} = \mathbf{1}$ 이며, 관측 행렬의 각 행도 확률 벡터이므로 $\mathbf{O}_a \mathbf{1} = \mathbf{1}$ 이다.

3. 신뢰 상태의 수학적 정의

3.1 이력(History)과 충분 통계량

정의 2 (행동-관측 이력). 시각 $t$ 에서의 이력(History) $h_t$ 는 초기 신뢰 상태와 그 이후의 행동-관측 시퀀스로 구성된다:

$h_t = (b_0, a_0, o_1, a_1, o_2, \ldots, a_{t-1}, o_t)$

이력의 길이는 시간 $t$ 에 대해 선형적으로 증가하며, 모든 가능한 이력의 수는 시간에 대해 기하급수적으로 증가한다. 이력 기반의 의사 결정은 계산적으로 비실용적이다.

정의 3 (신뢰 상태). 신뢰 상태(Belief State) $b_t$ 는 이력 $h_t$ 가 주어졌을 때 상태에 대한 사후 확률 분포이다:

$b_t(s) = \Pr(s_t = s \mid h_t), \quad \forall s \in \mathcal{S}$

신뢰 상태는 다음의 조건을 만족하는 확률 벡터이다:

$b_t \in \Delta^{|\mathcal{S}|-1} = \left\{ b \in \mathbb{R}^{|\mathcal{S}|} \;\middle|\; b(s) \geq 0, \; \sum_{s \in \mathcal{S}} b(s) = 1 \right\}$

여기서 $\Delta^{|\mathcal{S}|-1}$ 은 $(|\mathcal{S}|-1)$ -차원 확률 단체(Probability Simplex)이다.

정리 1 (충분 통계량). 신뢰 상태 $b_t$ 는 이력 $h_t$ 의 충분 통계량이다. 즉, 미래의 관측과 보상은 $b_t$ 와 현재 행동 $a_t$ 가 주어지면 이력 $h_t$ 에 조건부 독립이다:

$\Pr(o_{t+1}, s_{t+1}, r_{t} \mid h_t, a_t) = \Pr(o_{t+1}, s_{t+1}, r_{t} \mid b_t, a_t)$

이 정리의 중요성은 기하급수적으로 증가하는 이력 대신 고정 차원의 신뢰 상태만으로 최적 의사 결정이 가능함을 보장하는 데 있다.

3.2 베이즈 신뢰 갱신의 엄밀한 유도

에이전트가 신뢰 상태 $b$ 에서 행동 $a$ 를 실행하고 관측 $o$ 를 수신했을 때, 갱신된 신뢰 상태 $b' = \tau(b, a, o)$ 를 유도한다.

단계 1: 사전 예측(Prediction). 행동 $a$ 의 실행 후, 관측 수신 전의 예측 분포를 계산한다:

$\bar{b}(s') = \sum_{s \in \mathcal{S}} T(s, a, s') b(s)$

이는 전이 역학에 의한 신뢰 상태의 순방향 전파(Forward Propagation)이다. 벡터 형태로 $\bar{\mathbf{b}} = \mathbf{T}_a^\top \mathbf{b}$ 이다.

단계 2: 관측 갱신(Update). 관측 $o$ 를 수신한 후, 베이즈 규칙을 적용한다:

$b'(s') = \frac{O(s', a, o) \cdot \bar{b}(s')}{\Pr(o \mid b, a)} = \frac{O(s', a, o) \sum_{s \in \mathcal{S}} T(s, a, s') b(s)}{\sum_{s'' \in \mathcal{S}} O(s'', a, o) \sum_{s \in \mathcal{S}} T(s, a, s'') b(s)}$

정규화 상수(관측 우도)는 다음과 같다:

$\Pr(o \mid b, a) = \sum_{s' \in \mathcal{S}} O(s', a, o) \sum_{s \in \mathcal{S}} T(s, a, s') b(s)$

벡터 형태의 표현. 관측 $o_k$ 에 대한 대각 행렬 $\mathbf{D}_{a,o_k} = \text{diag}(O(s_1, a, o_k), \ldots, O(s_n, a, o_k))$ 를 정의하면:

$\mathbf{b}' = \frac{\mathbf{D}_{a,o_k} \mathbf{T}_a^\top \mathbf{b}}{\mathbf{1}^\top \mathbf{D}_{a,o_k} \mathbf{T}_a^\top \mathbf{b}}$

이 표현은 신뢰 갱신의 계산 구현에 직접 활용된다.

4. 신뢰 상태의 기하학적 구조

4.1 신뢰 단체(Belief Simplex)

신뢰 상태 공간 $\Delta^{n-1}$ 은 $n$ 차원 유클리드 공간 $\mathbb{R}^n$ 에 내장된 $(n-1)$ 차원 볼록 다면체(Convex Polytope)이다. $n = |\mathcal{S}|$ 일 때:

꼭짓점(Vertex): $n$ 개의 확정 신뢰 상태 $e_i = (0, \ldots, 1, \ldots, 0)$ (상태 $s_i$ 에 확률 1 할당)
변(Edge): 두 상태 사이의 혼합 분포
면(Face): 상태의 부분집합에 대한 분포

확률 단체의 중심은 균등 분포 $b_{\text{uniform}} = (1/n, \ldots, 1/n)$ 이며, 이는 최대 불확실성 상태에 대응한다.

4.2 신뢰 갱신의 기하학

신뢰 갱신 연산자 $\tau(b, a, o)$ 는 단체 $\Delta^{n-1}$ 에서 자기 자신으로의 사상이다. 이 사상의 기하학적 특성은 다음과 같다:

비선형(Nonlinear): 정규화 단계로 인해 $\tau$ 는 $b$ 에 대해 비선형이다.
단체 보존(Simplex-Preserving): $\tau$ 의 출력은 항상 유효한 확률 분포이다.
수축적(Contractive): 정보량이 큰 관측(관측 함수의 불균등이 큰 경우)은 신뢰 상태를 단체의 꼭짓점 방향으로 수축시킨다. 이는 불확실성 감소에 대응한다.

4.3 정보 이론적 해석

신뢰 상태의 불확실성은 섀넌 엔트로피(Shannon Entropy)로 정량화할 수 있다:

$H(b) = -\sum_{s \in \mathcal{S}} b(s) \log b(s)$

관측을 수신하면 일반적으로 엔트로피가 감소하며, 이는 에이전트의 환경에 대한 지식 증가를 반영한다. 정보 이득(Information Gain)은 다음과 같이 정의된다:

$\text{IG}(b, a) = H(b) - \mathbb{E}_{o}[H(\tau(b, a, o))] = H(b) - \sum_{o \in \Omega} \Pr(o \mid b, a) H(\tau(b, a, o))$

정보 이득은 항상 비음수이며(데이터 처리 부등식에 의해), 이는 관측이 평균적으로 불확실성을 증가시키지 않음을 의미한다.

5. 신뢰 MDP로의 형식적 변환

정리 2 (POMDP와 신뢰 MDP의 동치성). POMDP $\mathcal{P} = \langle \mathcal{S}, \mathcal{A}, T, R, \Omega, O, \gamma \rangle$ 는 다음의 연속 상태 공간 MDP(신뢰 MDP) $\mathcal{M}_b = \langle \mathcal{B}, \mathcal{A}, \tau_b, \rho, \gamma \rangle$ 와 동치이다:

상태 공간: $\mathcal{B} = \Delta^{|\mathcal{S}|-1}$ (신뢰 단체)
행동 공간: $\mathcal{A}$ (원래의 행동 공간)
전이 역학: 확률적 전이 $b \xrightarrow{a, o} b' = \tau(b, a, o)$ , 여기서 관측 $o$ 는 $\Pr(o \mid b, a)$ 의 확률로 발생
보상: $\rho(b, a) = \sum_{s \in \mathcal{S}} b(s) R(s, a) = \mathbf{b}^\top \mathbf{R}_a$

신뢰 MDP에서의 벨만 최적 방정식:

$V^*(b) = \max_{a \in \mathcal{A}} \left[ \rho(b, a) + \gamma \sum_{o \in \Omega} \Pr(o \mid b, a) V^*(\tau(b, a, o)) \right]$

이 변환에 의해 POMDP의 최적 정책은 $\pi^*: \mathcal{B} \rightarrow \mathcal{A}$ , 즉 신뢰 상태에서 행동으로의 매핑이 된다.

6. 최적 가치 함수의 PWLC 구조

6.1 α-벡터 표현

정리 3 (Smallwood-Sondik 정리). 유한 수평 POMDP에서 잔여 시간 $t$ 의 최적 가치 함수 $V_t^*(b)$ 는 유한 개의 α-벡터(alpha-vector)의 점별 최대(Pointwise Maximum)로 표현되는 구분선형 볼록(Piecewise Linear and Convex, PWLC) 함수이다:

$V_t^*(b) = \max_{\alpha \in \Gamma_t} \alpha^\top b = \max_{\alpha \in \Gamma_t} \sum_{s \in \mathcal{S}} \alpha(s) \cdot b(s)$

여기서 $\Gamma_t = \{\alpha_1, \alpha_2, \ldots, \alpha_{|\Gamma_t|}\}$ 는 α-벡터의 유한 집합이다.

각 α-벡터 $\alpha \in \mathbb{R}^{|\mathcal{S}|}$ 는 특정 조건부 계획(Conditional Plan)에 대응하며, $\alpha(s)$ 는 실제 상태가 $s$ 일 때 해당 조건부 계획을 따를 경우의 기대 누적 보상이다.

6.2 α-벡터의 기하학적 의미

신뢰 단체 $\Delta^{n-1}$ 위에서 각 α-벡터 $\alpha^\top b$ 는 초평면(Hyperplane)을 정의한다. 가치 함수 $V_t^*(b)$ 는 이 초평면들의 상한(Upper Envelope)이며, 이는 볼록 구분선형 함수를 구성한다.

α-벡터 $\alpha$ 가 신뢰 단체의 영역(Region) $\mathcal{R}_\alpha \subseteq \Delta^{n-1}$ 에서 최대값을 달성하면, $\mathcal{R}_\alpha$ 는 볼록 다면체이고, 이 영역에서 최적 행동은 $\alpha$ 에 대응하는 행동이다. 인접한 영역의 경계에서 최적 행동이 전환되며, 이 경계는 두 α-벡터가 동일한 가치를 제공하는 초평면 $\alpha_i^\top b = \alpha_j^\top b$ 이다.

6.3 α-벡터 수의 증가

유한 수평 문제에서 α-벡터 집합 $\Gamma_t$ 의 크기는 잔여 시간 $t$ 가 증가함에 따라 기하급수적으로 증가할 수 있다:

$|\Gamma_1| \leq |\mathcal{A}|, \quad |\Gamma_t| \leq |\mathcal{A}| \cdot |\Gamma_{t-1}|^{|\Omega|}$

따라서 $|\Gamma_t| \leq |\mathcal{A}|^{(|\Omega|^t - 1)/(|\Omega| - 1)}$ 이 되어, 정확한 POMDP 해법의 계산 비용이 이중 지수적(Doubly Exponential)으로 증가한다. 이 증가율이 POMDP의 정확한 해법이 중간 규모 이상의 문제에서 비실용적인 근본적 원인이다.

7. 신뢰 상태의 로봇 임무 계획 적용

7.1 센서 융합과 신뢰 갱신

다수의 센서를 탑재한 로봇에서 각 센서의 관측은 독립적인 관측 함수로 모델링하고, 베이즈 갱신을 순차적으로 적용하여 융합된 신뢰 상태를 구성할 수 있다. 센서 $k$ 의 관측 함수를 $O_k(s', a, o_k)$ 라 하면:

$b'(s') \propto \left( \prod_{k=1}^{K} O_k(s', a, o_k) \right) \sum_{s} T(s, a, s') b(s)$

이 다중 센서 융합은 개별 센서의 한계를 보완하여 신뢰 상태의 정확도를 향상시킨다.

7.2 파티클 필터 기반 신뢰 근사

상태 공간이 대규모인 경우, 신뢰 상태를 확률 벡터로 직접 유지하는 것이 비현실적이다. 파티클 필터(Particle Filter)를 사용하여 신뢰 상태를 $N$ 개의 가중 입자(Weighted Particle)의 집합으로 근사할 수 있다:

$b(s) \approx \sum_{i=1}^{N} w_i \cdot \delta(s - s^{(i)})$

여기서 $s^{(i)}$ 는 $i$ 번째 입자의 상태이고, $w_i$ 는 정규화된 가중치이며, $\delta$ 는 디랙 델타 함수이다. 파티클 필터 기반 POMDP 해법은 대규모 로봇 임무 계획에서 실용적인 신뢰 상태 유지 방법을 제공한다.

7.3 히스토그램 기반 신뢰 표현

이산 상태 공간에서 신뢰 상태를 히스토그램(Histogram)으로 직접 표현하는 방법이다. 상태 공간의 크기가 관리 가능한 경우(수천 이하), 각 상태에 대한 확률 값을 배열로 유지하고 베이즈 갱신을 정확하게 수행할 수 있다. 계산 복잡도는 $O(|\mathcal{S}|^2)$ 이며, 정확한 신뢰 상태를 보장한다.

8. 참고 문헌

Åström, K. J. (1965). “Optimal Control of Markov Processes with Incomplete State Information.” Journal of Mathematical Analysis and Applications, 10(1), pp. 174-205.
Smallwood, R. D. & Sondik, E. J. (1973). “The Optimal Control of Partially Observable Markov Decision Processes over a Finite Horizon.” Operations Research, 21(5), pp. 1071-1088.
Kaelbling, L. P., Littman, M. L., & Cassandra, A. R. (1998). “Planning and Acting in Partially Observable Stochastic Domains.” Artificial Intelligence, 101(1-2), pp. 99-134.
Cassandra, A. R. (1998). Exact and Approximate Algorithms for Partially Observable Markov Decision Processes. Ph.D. Thesis, Brown University.
Thrun, S., Burgard, W., & Fox, D. (2005). Probabilistic Robotics. MIT Press.

본 절은 POMDP의 공리적 정의, 신뢰 상태의 수학적 구조, 베이즈 신뢰 갱신, α-벡터 표현의 PWLC 구조, 및 로봇 임무 계획에서의 신뢰 상태 적용을 다루었다. v1.0