부분관측 마르코프 결정 과정

1. 개요[편집]

부분관측 마르코프 결정 과정 Partially Observable Markov Decision Process
약칭	POMDP
구성	(S, A, P, R, Ω, O, γ) — 7개 쌍
핵심 아이디어	믿음 상태 b(s) 위의 연속 MDP로 환원
가치함수 구조	믿음 공간 위 조각별 선형 · 볼록 (α-벡터)
복잡도	유한 지평 PSPACE-난해 / 무한 지평 결정 불가능

상태를 모르면? 상태에 대한 믿음을 상태로 삼으면 된다. 대신 상태 공간이 이산 유한에서 연속 무한 차원 확률 단체로 승격된다.

부분관측 마르코프 결정 과정(POMDP)은 마르코프 결정 과정에 관측 모형을 추가해, 에이전트가 참 상태를 직접 보지 못하고 잡음 낀 관측만 받는 상황을 다루는 순차 의사결정 형식화다. MDP의 다섯 쌍 $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$에 관측 집합 $\Omega$와 관측 확률 $O(o \mid s', a) = P(o_t = o \mid s_t = s', a_{t-1} = a)$를 더한 일곱 쌍이 정의다.

이게 왜 별도 문서를 가질 만큼 큰 문제냐면, 현실이 거의 전부 POMDP이기 때문이다. 로봇은 자기 위치를 모르고 레이저 거리만 안다. 정비 담당자는 베어링의 손상 정도를 모르고 진동 스펙트럼만 안다. 자율주행차는 트럭 뒤에 무엇이 있는지 모르고 가려진 시야만 갖는다. MDP를 배우고 나서 현장에 나가면 “그런데 $s$를 어떻게 알죠?”라는 질문에 곧바로 부딪히는데, 그 질문에 대한 정직한 답이 POMDP다. 대가는 계산량이고, 이 문서의 절반은 그 대가에 관한 이야기다.

2. 믿음 상태 — 충분통계량으로서의 확률분포[편집]

관측이 상태를 다 말해주지 않으면 $o_t$ 하나만 보고 행동을 고르는 것은 최적이 아니다. 과거 전체 이력 $h_t = (a_0, o_1, \ldots, a_{t-1}, o_t)$가 필요한데, 이력은 시간에 따라 무한히 길어진다. POMDP 이론의 출발점은 이력 전체를 요약하는 충분통계량이 존재한다는 정리다. 바로 믿음 상태(belief state)

$$b_t(s) = P\big(s_t = s \mid h_t\big), \qquad \sum_{s \in \mathcal{S}} b_t(s) = 1$$

이다. $b_t$만 알면 이력을 통째로 버려도 최적성을 잃지 않는다. 그리고 $b_t$는 마르코프 성질을 만족한다 — $b_{t+1}$은 $b_t$, $a_t$, $o_{t+1}$만으로 결정된다. 즉 POMDP는 믿음 공간 위의 완전관측 MDP로 환원된다. 이론적으로는 문제가 풀린 셈이고, 실용적으로는 이제부터가 문제다. 상태가 $|\mathcal{S}|$개면 믿음 공간은 $(|\mathcal{S}|-1)$차원 확률 단체(simplex), 즉 연속 공간이다. 상태 100개짜리 장난감 문제도 99차원 연속 MDP가 된다.

3. 믿음 갱신은 그냥 베이즈 필터다[편집]

믿음 갱신식은 예측 한 번, 보정 한 번이다.

$$b'(s') = \eta\; O(o \mid s', a) \sum_{s \in \mathcal{S}} P(s' \mid s, a)\, b(s)$$

$\eta$는 정규화 상수다. 합 부분이 행동에 의한 예측(전이 모형 적용), 앞의 곱이 관측에 의한 보정(우도 곱하기). 이건 칼만 필터와 입자 필터가 하는 일과 문자 그대로 같은 계산이다. 상태가 이산이면 위 식을 표로 직접 돌리고(히스토그램 필터), 선형-가우시안이면 칼만 필터의 예측-갱신 사이클이 되며, 비선형·다봉이면 입자 구름으로 근사한다.

그래서 POMDP를 실제로 구현할 때 절반은 필터링 문제다. 센서 융합과 자료동화에서 쓰던 기법이 그대로 온다. 다만 결정적인 차이가 하나 있다. 순수 추정 문제에서 행동은 외생 변수지만, POMDP에서 행동은 믿음을 바꾼다. 벽에 다가가 거리를 재면 위치 불확실성이 줄고, 진단 장비를 붙이면 고장 상태의 엔트로피가 줄어든다. 보상이 없는 이런 정보 수집 행동을 자동으로 계획해 준다는 것이 POMDP의 진짜 가치다. 이걸 못 하는 근사는 아무리 빨라도 POMDP를 푼 게 아니다.

4. 가치함수는 조각별 선형이고 볼록하다[편집]

믿음 공간이 연속이라 가치함수 $V^{*}(b)$가 손댈 수 없어 보이지만, 소닉(Sondik, 1971)의 정리가 구조를 준다. 유한 지평 POMDP의 최적 가치함수는 믿음 위에서 조각별 선형이고 볼록하다. 즉 유한 개의 벡터 집합 $\Gamma = \{\alpha_1, \ldots, \alpha_m\}$이 존재해

$$V^{*}(b) = \max_{\alpha \in \Gamma} \sum_{s \in \mathcal{S}} \alpha(s)\, b(s) = \max_{\alpha \in \Gamma} \langle \alpha, b \rangle$$

로 쓸 수 있다. 각 $\alpha$-벡터는 하나의 조건부 계획(conditional plan)에 대응하고, 그 계획을 각 참 상태에서 실행했을 때의 기대 수익을 성분으로 갖는다. 볼록하다는 사실 자체가 해석을 준다 — 정보는 결코 손해가 아니다. 믿음이 뾰족할수록(꼭짓점에 가까울수록) 가치가 높고, 반반으로 헷갈리는 믿음이 골짜기 바닥이다.

벨만 백업은 이 표현 위에서 이렇게 쓰인다.

$$V^{*}(b) = \max_{a \in \mathcal{A}} \Big[\, \sum_{s} b(s) R(s,a) + \gamma \sum_{o \in \Omega} P(o \mid b, a)\, V^{*}(b^{a,o}) \,\Big]$$

문제는 폭발 속도다. 백업 한 번에 $\alpha$-벡터 개수가 $|\mathcal{A}| \cdot |\Gamma|^{|\Omega|}$까지 늘어난다. 지배당하는 벡터를 선형계획법으로 쳐내는 가지치기(증분 가지치기, Witness 알고리즘)를 매 단계 돌려야 하고, 그래도 상태 수십 개 · 지평 수십 스텝이 정확해의 현실적 한계다. 이론적으로도 유한 지평 POMDP의 최적 정책 계산은 PSPACE-난해이고, 무한 지평 문제는 아예 결정 불가능이라는 결과까지 있다.¹

5. 근사 해법 — 실전은 전부 여기에 있다[편집]

• QMDP — MDP로 $Q(s,a)$를 풀어 놓고 믿음으로 평균 낸다: $Q(b,a) = \sum_s b(s) Q_{\text{MDP}}(s,a)$. 계산이 사실상 공짜지만 한 스텝 뒤엔 불확실성이 사라진다고 가정하는 근사라, 정보 수집 행동을 절대 고르지 않는다. 관측이 이미 충분히 좋을 때만 쓸 만한 베이스라인.²
• 점기반 가치반복(PBVI, Perseus, SARSOP) — 믿음 공간 전체가 아니라 도달 가능한 믿음점을 유한 개 표본추출해서 그 점들에서만 백업을 돌린다. 각 점마다 $\alpha$-벡터 하나씩만 유지하니 폭발이 막힌다. SARSOP은 여기에 최적 정책 하에 실제로 도달하는 영역만 좁혀 탐색하는 가지치기를 얹어, 상태 수천 개 규모까지 실용화했다.
• POMCP / DESPOT — 믿음 상태 위에서 도는 몬테카를로 트리 탐색이다. 믿음을 입자 집합으로 들고, 시뮬레이터로 롤아웃을 굴리며 이력 트리를 UCT로 키운다. 전이·관측 확률의 명시적 표를 요구하지 않고 표본을 뽑을 수 있는 생성 모형(시뮬레이터) 하나면 된다는 점이 결정적이다. 이 위키 입장에서는 물리 엔진이나 CFD 솔버가 곧 그 생성 모형이라는 뜻이기도 하다.³
• 모형 프리 우회 — 믿음을 명시적으로 계산하지 않고, 순환 신경망의 은닉 상태가 이력 요약을 알아서 배우게 두는 방식(DRQN, R2D2 계열). Q러닝을 관측 이력에 그대로 얹는 셈이라 이론적 보증은 없지만, 상태 공간을 모형화할 수 없는 문제에서는 이쪽이 유일한 선택지다.

6. 어디에 쓰이나[편집]

• 로봇 위치추정과 능동 센싱 — 몬테카를로 위치추정(몬테카를로 위치추정)이 믿음 갱신이고, 그 위에 “어디로 가면 자기 위치를 가장 빨리 확정할 수 있나”를 계획하는 것이 능동 센싱이다. 복도가 다 똑같이 생긴 건물에서 로봇이 굳이 문 앞까지 가 보는 행동이 POMDP 정책의 전형적인 산물.
• 진단과 정비 계획 — 설비의 열화 상태는 못 보고 진동·온도·오일 분석만 본다. 검사(비용은 들지만 정보를 준다) / 계속 운전 / 교체 중 하나를 고르는 문제는 교과서적 POMDP다. 기계 정비 문제(machine replacement problem)는 이 분야 고전 벤치마크.
• 대화 시스템 — 사용자의 의도는 은닉 상태, 음성인식 결과는 잡음 낀 관측이다. 되묻기(clarification)는 보상이 없는 순수 정보 수집 행동이고, POMDP는 되묻는 비용과 오해의 비용을 저울질해 그 타이밍을 정한다.
• 자율주행의 가림 상황 — 주차된 트럭 뒤에서 튀어나올지 모르는 보행자는 관측되지 않는 상태다. 존재 확률에 대한 믿음을 유지하며 감속량을 정하는 것이 POMDP 정식화이고, 실무에서는 짧은 지평의 온라인 POMDP 해법을 모델 예측 제어처럼 매 주기 다시 푸는 방식으로 돌린다.
• 탐사·수색 — 광물 시추 위치 선정, 조난자 수색 경로 계획처럼 “정보를 사는 데 돈이 드는” 문제 전반.

$\Omega$가 상태와 일대일이면 POMDP는 MDP로 되돌아가고, 행동을 없애면 그냥 은닉 마르코프 모형 추론 문제 — 즉 비터비 알고리즘과 순방향-역방향 알고리즘의 무대 — 가 된다. POMDP는 그 두 세계를 한 틀에 합친 것이고, 합친 값은 정확히 계산 복잡도로 청구된다.⁴

7. 관련 문서[편집]

• 마르코프 결정 과정 — 관측이 완전할 때의 원형
• 입자 필터 · 칼만 필터 — 믿음 갱신의 실제 구현
• 몬테카를로 트리 탐색 — POMCP의 뼈대
• Q러닝 · 강화 학습 · 심층 학습
• 비터비 알고리즘 · 은닉 마르코프 모형
• 센서 융합 · 자료동화 · 관성항법
• 동적 계획법 · 볼록 최적화
• 불확실성 정량화 · 통계
• 모델 예측 제어 · 물리 엔진

8. Footnotes[편집]

1. 파파디미트리우와 치치클리스(1987)가 유한 지평 POMDP 정책 존재 판정이 PSPACE-완전임을 보였고, 이후 무한 지평 문제의 결정 불가능성 결과도 나왔다. 요약하면 “정확히 푸는 건 포기해라”는 정리를 30년째 인용하고 있는 셈이다. ↩

2. QMDP가 정보 수집 행동을 못 고른다는 것은 버그가 아니라 가정의 논리적 귀결이다. “한 스텝 뒤엔 다 알게 될 것”이라고 믿는 에이전트에게 정보를 사는 행동은 순수한 낭비로 보인다. 근사의 가정을 안 읽고 결과만 보면 에이전트가 게을러 보이는데, 게으른 건 우리가 세운 가정이다. ↩

3. 입자 필터로 믿음을 근사하는 POMCP는 입자 고갈(particle depletion)을 그대로 물려받는다. 예상 못 한 관측이 들어오면 살아남는 입자가 한 줌으로 줄고, 그때부터 정책은 잘못된 믿음 위에서 아주 자신 있게 틀린 행동을 고른다. 현장에서 이 증상은 대체로 “로봇이 갑자기 확신에 차서 벽으로 돌진”으로 관측된다. ↩

4. MDP를 배운 사람이 POMDP를 처음 보면 대개 “믿음 상태 위의 MDP니까 그냥 MDP 알고리즘 쓰면 되는 거 아님?”이라고 반응한다. 맞는 말이고, 그 MDP의 상태 공간이 연속 무한 차원이라는 사소한 부작용만 감수하면 된다. ↩