Weighted Moment-SoS approach to POMDPs with polynomial data
Published in HAL, 2025
We present a novel infinite-dimensional linear programming (IDLP) based method for solving Partially Observable Markov Decision Processes (POMDPs) via Moment-SoS hierarchies. Standard belief-state IDLP formulations yield rational dynamics via the Bayesian filter, obstructing direct use of Moment-SoS relaxations. To address this, we reformulate the POMDP over unnormalized beliefs, yielding polynomial system dynamics. This formulation, however, breaks contractivity of the Bellman operator, rendering conventional IDLPs ill-posed.
Our key contribution is to restore contractivity by introducing an ℓ1-based Lyapunov weight and formulating the control problem in a weighted Banach space. The resulting Bellman operator becomes contractive, yielding a well-posed IDLP with strong duality. This leads to a generalized moment problem (GMP) formulation, solvable via Moment-SoS relaxations. We validate the method on the two-armed bandit and tiger problems, generating approximations for optimal policies and optimal values.
Recommended citation: Konstantin Avrachenkov, Lucas Gamertsfelder, Bernard Mourrain. (2024). " Weighted Moment-SoS approach to POMDPs with polynomial data ." HAL.
Download Paper