유한 시간 목표를 갖는 다중 환경 부분 관찰 마르코프 결정 과정 (MEPOMDP)

Multi-Environment POMDPs with Finite-Horizon Objectives

부분 관찰 마르코프 결정 과정 (POMDP)은 한 에이전트가 확률적 환경과 상호 작용하며, 현재 상태에 대한 부분적인 정보만 받는 시스템입니다. 다중 환경 POMDP (MEPOMDP)에서 초기 상태는 알려지지 않으며, 적대적으로 선택되었다고 가정합니다. 본 연구에서는 유한 시간 목표를 갖는 MEPOMDP에서 최적의 가치와 정책을 계산하는 데 중점을 둡니다. 이 문제는 POMDP에서 PSPACE-완전 문제로 알려져 있습니다. 우리의 주요 결과는 다음과 같습니다: (1) MEPOMDP의 더 일반적인 설정에서도 PSPACE-완전임을 입증합니다. (2) 실제적인 알고리즘을 제시하고, 고전적인 벤치마크에서 평가하여, 기존에 알려진 알고리즘보다 훨씬 뛰어난 성능을 보입니다.

Partially Observable Markov Decision Processes (POMDPs) are systems in which one agent interacts with a stochastic environment, and receives only partial information about the current state. In a multi-environment POMDP (MEPOMDP), the initial state is unknown, and assumed to be adversarially chosen. In this work we focus on computing the optimal value and policy in MEPOMDPs with finite-horizon objectives. That problem is known to be PSPACE-complete in POMDPs. Our main results are as follows: (1) we establish that it is also PSPACE-complete in the more general setting of MEPOMDPs; (2) we present a practical algorithm and evaluate it on classical benchmarks, significantly outperforming the only previously known algorithm.