MDP·POMDP·Belief와 정보 획득

상태를 알고 행동하는가, 상태의 분포로 행동하는가

완전 관측 Markov 의사결정 과정은 행동을 고르기 전에 현재 상태를 알려줍니다. 모형은 상태, 행동, 전이 확률과 비용을 지정합니다. 정책은 알려진 상태와 남은 시간을 보고 행동을 비교합니다. 앞의 Bellman 단원에서는 유한 MDP에서 이 비교를 정확히 계산했습니다.

부분 관측 MDP에서는 관측이 상태를 직접 알려주지 않습니다. 의사결정자는 가능한 상태들의 분포인 belief를 사용합니다. Belief는 단순히 마지막 관측값이나 모형 없는 신뢰도 점수, 숨은 물리 상태 자체가 아닙니다. 올바른 전이·관측 모형을 알면 행동과 관측 이력의 관련 정보를 요약합니다. 유한 시간 정책에는 남은 의사결정 예산도 함께 필요합니다.

숨은 상태의 관측·중단 문제를 정한다

이 실습에서는 이진 숨은 변수 Z가 마지막 추측 전까지 고정됩니다. 사전 belief는 b=P(Z=1)입니다. 0으로 추측하면 Z=1일 때만 손실 1을 받으므로 기대 손실은 b입니다. 1로 추측하면 기대 손실은 1-b입니다. 어느 쪽이든 추측하면 작업이 종료되고 이후 비용은 0입니다.

관측 한 번에는 비용 c가 들고 정확도 eta=P(Y=Z)의 이진 센서가 Y를 반환합니다. Z가 주어지면 반복 센서 잡음들은 독립입니다. 관측은 Z를 바꾸지 않고 의사결정자가 가진 정보를 바꿉니다. 최대 H번 더 관측할 수 있으며 추측은 언제든 가능합니다. H=0은 최종 결정을 하지 않아도 된다는 뜻이 아니라 지금 추측해야 한다는 뜻입니다. 유한한 관측 문제이므로 할인율은 사용하지 않습니다.

비교 대상인 완전 관측 제어기는 Z를 알고 있으므로 비용 0으로 맞게 추측합니다. 이는 정보의 이점이며 부분 관측 제어기가 사용할 수 있는 알고리즘은 아닙니다. POMDP 정책에 숨은 정답을 제공하지 않습니다.

예측한 다음 관측으로 조건화한다

일반 POMDP에서는 전이 모형 T로 다음 상태 분포를 먼저 예측한 뒤 관측 모형 O로 조건화합니다.

$$b'(s')=\frac{O(y\mid s',a)\sum_s T(s'\mid s,a)b(s)} {\sum_j O(y\mid j,a)\sum_s T(j\mid s,a)b(s)}.$$

분모는 관측의 확률이며 사후확률을 정의하려면 양수여야 합니다. 이 실습에서 관측 행동의 Z 전이는 항등이므로

$$m_1=\eta b+(1-\eta)(1-b),\qquad b_1=\frac{\eta b}{m_1},$$ $$m_0=(1-\eta)b+\eta(1-b),\qquad b_0=\frac{(1-\eta)b}{m_0}$$

입니다. 선택한 관측의 질량이 0이면 사후확률은 정의되지 않습니다. Readout은 미정 값을 표시하고 도식은 빈 점선 사후 프레임을 보여줍니다. Epsilon을 넣어 가상의 사후확률을 만들지 않습니다. 기대값에서는 그 불가능한 가지를 질량 0으로 제외합니다.

사후 비율에서는 우도를 공통 크기로 나누어 불필요한 underflow를 줄입니다. 같은 작은 위험을 두 개의 반확률로 나눠 더할 때 불필요하게 사라지지 않도록 상수를 보존하는 기대값 계산도 사용합니다. 같은 모형을 수치적으로 평가하는 방법이며 확률을 임의로 평활화하거나 관측을 추가하는 것은 아닙니다.

정보 획득도 Bellman 행동으로 만든다

바로 추측하는 위험은 V0(b)=min(b,1-b)입니다. H가 양수이면 두 중단 행동과 관측 후 조건부 최적 행동을 비교합니다.

$$V_H(b)=\min\left\{b,1-b, c+\sum_{y:m_y>0}m_y V_{H-1}(b_y)\right\}.$$

정책은 (H,b)에서 행동을 고르고 관측 뒤 다음 행동을 다시 고릅니다. 결과와 관계없이 무조건 H번 관측하라는 수열과 다릅니다. 첫 행동 코드는 0은 추측0, 1은 추측1, 2는 관측입니다. 부동소수점 값이 정확히 같으면 이 순서로 택합니다. 동률 근처의 작은 수치 차이를 실질적으로 큰 행동 우위로 해석하지 마세요.

즉시 중단이 항상 가능하므로 이 모형에서 최적 계획 비용은 즉시 추측 위험보다 크지 않습니다. 관측 기회의 최댓값을 늘려도 사용하지 않을 수 있으므로 최적 비용은 증가하지 않습니다. 그러나 관측을 강제로 추가하면 비용이 들 수 있고 정보도 유용하지 않을 수 있습니다.

표본 이력을 상상하지 않고 그림을 읽는다

위 막대는 선택한 가상 관측의 사전·사후 분포를 보여줍니다. 파랑은 Z=1, 주황은 Z=0의 질량입니다. 선택 Y는 한 번 관측했다고 가정한 계산입니다. H=0이거나 최적 정책이 중단을 택했더라도 이 가상 갱신을 보여주며, 실제 정책이 관측을 획득했다고 주장하지 않습니다.

아래 그래프의 가로축은 시간이 아니라 belief입니다. 파랑은 선택한 H의 최적 기대 비용, 주황은 즉시 추측의 오판 위험입니다. 점은 선택한 사전확률을 표시합니다. 201개 belief를 계산해 선분으로 연결하므로 작은 정책 경계는 표본 사이에 있을 수 있지만 선택 belief의 값은 정확한 유한 재귀로 계산합니다. 표는 같은 사전에서 H를 바꾼 결과를 비교합니다.

기대 관측 횟수와 최종 오판 확률은 서로 다른 readout입니다. 두 값을 결합해 목적함수를 확인할 수 있습니다.

$$V_H(b)=c\,\mathbb E[N_{listen}]+\Pr(\text{terminal guess is wrong}).$$

최적 정책에서 총비용이 작아진 것은 관측을 더 하면서 오판을 줄인 절충일 수 있습니다. 두 성분을 각각 최소화했다는 뜻은 아닙니다.

조건부 계획의 비용이 오목한 이유

모든 관측 뒤의 행동까지 포함하는 조건부 계획을 하나 고정해 봅시다. 두 숨은 상태에서 그 계획의 기대 총비용을 alpha0,alpha1이라고 하면 사전으로 평균한 비용은

$$C_\alpha(b)=(1-b)\alpha_0+b\alpha_1$$

로 belief에 선형입니다. 중단 계획은 (0,1), (1,0)의 벡터를 갖습니다. Y=0 뒤의 계획 벡터가 a이고 Y=1 뒤가 d이면 한 번 관측하는 계획은

$$\alpha_0=c+\eta a_0+(1-\eta)d_0,\qquad \alpha_1=c+(1-\eta)a_1+\eta d_1$$

입니다. 유한한 계획 집합에서 최소를 취하므로 조각별 선형인 오목한 아래 포락선을 얻습니다. 비용 최소화라는 부호가 중요합니다. 보상 최대화에서 사용하는 볼록한 위 포락선을 그대로 옮기면 틀립니다.

H=0,1,2,3의 가지치기하지 않은 계획 수는 M_H=2+M_(H-1)²에 따라 2,6,38,1446개입니다. 테스트에서는 이 계획들을 별도로 열거한 값과 실제 Bayes 관측 트리 재귀를 비교합니다. 작은 모형이므로 정확히 열거할 수 있으며 일반 POMDP에는 더 효율적인 표현과 근사가 필요합니다.

사후확률과 한 번 관측의 손계산 문제

b=0.5,eta=0.8,c=0.05,H=1로 놓습니다. 두 관측의 확률, 사후 belief와 즉시 추측·한 번 관측 중 최적 선택을 먼저 직접 계산해 보세요.

해설. 두 관측의 확률은 각각 0.5입니다. Y=1이면 사후 b=0.8, Y=0이면 b=0.2입니다. 어느 사후에서든 확률이 큰 쪽을 추측하면 오판 확률은 0.2입니다. 따라서 관측 비용은 0.05+0.2=0.25이며 바로 추측하는 비용 0.5보다 작습니다. 첫 행동은 관측입니다.

같은 매개변수에서 H=3으로 바꾸면, 두 번 관측한 결과가 같을 때 중단하고 다를 때 한 번 더 관측하는 최적 계획을 생각할 수 있습니다. 두 결과가 다를 확률은 2*(0.8)(0.2)=0.32이므로 기대 관측 횟수는 2.32입니다. 최종 오판 확률은 0.104이고 총비용은 0.052.32+0.104=0.22입니다.

이 예제는 계획의 효과도 보여줍니다. belief가 0.8일 때 한 번 더 관측하는 것으로는 비용을 정당화할 만큼 오판이 줄지 않으므로 V1(0.8)=0.2입니다. 그러나 두 번까지 더 관측할 기회가 있으면 V2(0.8)=0.17입니다. 한 단계 정보 가치만 보는 규칙은 중단하더라도, 이후 관측 결과에 따라 달라지는 계획은 지금 관측할 이유를 만들 수 있습니다.

정보가 없는 센서·완벽한 센서·불가능한 관측

eta=0.5이면 어떤 관측도 사전을 바꾸지 않습니다. 양의 비용을 지불하는 관측은 H를 늘려도 도움이 되지 않습니다. eta=1이고 두 상태의 사전 질량이 양수이면 한 번 관측으로 Z를 정확히 알 수 있지만, 그것을 획득할 가치는 현재 오판 위험과 c의 비교에 달렸습니다.

b=0,eta=1,Y=1이면 그 관측은 불가능하여 사후확률이 없습니다. 이미 Z=0을 알고 있으므로 정책은 비용 0으로 중단할 수 있습니다. 조건부 계산의 미정 값이 값함수 자체의 실패를 뜻하지 않습니다. 이 경계 사례로 상태 지식, 센서 품질, 관측 support와 정보 가치를 구분하세요.

AI 연구로의 연결

Belief 모형은 필터링과 의사결정을 연결합니다. 관측은 entropy를 줄이기 때문만이 아니라 미래 행동을 바꾸기 때문에 중요할 수 있습니다. 학습한 world model, 능동 지각과 부분 관측 에이전트에는 모형 오차·이력 표현·근사 문제가 추가됩니다. 정확한 belief의 충분성은 명시한 모형을 전제로 하며, 학습한 순환 임베딩이 자동으로 보정된 Bayes belief가 되는 것은 아닙니다. 이 작은 모형은 그런 문제들과 알려진 POMDP의 계산을 구분하는 기준입니다.

원전과 읽을거리

Kaelbling·Littman·Cassandra의 Planning and acting in partially observable stochastic domains, Artificial Intelligence 101 (1998)은 belief-MDP와 조건부 계획의 넓은 틀을 제공합니다. 이 교재의 유한 0/1 손실 관측 모형, 비용 최소화 유도, 수치 예제, 그림과 독립 검산은 직접 구성했습니다.