Constant-Gap PSPACE-Completeness for Finite-Horizon POMDPs with a Fixed Permutation Dilation
Ryunosuke Hirata · Zenodo (CERN European Organization for Nuclear Research) · 2026
This preprint studies finite-horizon planning in partially observable Markov decision processes under a simultaneous collection of strong structural restrictions. The controller has two actions, receives one of four observations represented by two public bits, and makes a final binary identification decision with zero-one terminal reward. The horizon is unary and the hidden state space is explicit and polynomially bounded. The transition-observation kernel is induced by sampling a fresh fair public bit, resetting a binary port, and applying the same explicitly tabulated permutation in every round. It is PSPACE-complete to distinguish instances with optimal value V = 1* from those with V ≤ 2/3*, even when the complete preterminal public transcript is exactly independent of both the hidden hypothesis and the private verifier seed. The lower bound uses an exact reversible compiler from constant-query random probabilistically checkable debate systems and preserves legal strategy values in both directions. The compiled dynamics are then expressed as an ordinary joint transition-observation kernel, converted to separated transition/observation form, and mapped to Bayesian identification reward. A polynomial-space unnormalized-belief recursion gives the matching upper bound. The result is a restricted normal form for ordinary finite-horizon POMDP planning rather than a new POMDP model. Status: Preprint. Not peer-reviewed.