본 논문은 불완전한 정보 하에서의 의사결정 문제를 다루는 부분적으로 관측 가능한 마르코프 의사결정 과정(POMDP)에 대해 논의한다. POMDP의 최적 해를 구하는 것은 일반적으로 어려운 문제이지만, 최근 온라인 트리 탐색 솔버를 이용하여 중소 규모 문제에 대한 근사 솔버의 확장에 상당한 진전이 있었다. 본 논문에서는 이러한 근사 솔버의 한계를 극복하고자, 이산 POMDP에서 근사해와 최적해 사이의 결정론적 관계를 유도한다. 어떤 시점에서든 기존 해와 최적해 사이의 경계를 도출할 수 있음을 보이고, 이를 통해 새로운 알고리즘을 위한 방안을 제시하며, 특정 구조를 가진 기존 알고리즘에 적용하여 결정론적 보장을 제공할 수 있음을 보인다. 이는 해의 품질을 인증할 뿐만 아니라, 결정론적 보장에 기반한 의사결정이 기존 알고리즘보다 우수한 성능을 낼 수 있음을 보여준다.
