Can the solution to a POMDP be found using linear programming?

Question

It is known that Markov decision processes (MDPs) can be solved using linear programming (see page 24 of Carlos Guestrin's PhD dissertation). The linear program is:

$$min_{V(x)} \sum_x \alpha(x)V(x)\\ \text{subject to: } V(x) \ge R(x,a) + \gamma\sum_{x'}P(x'|x,a)V(x')\text{ for all }x\in X, a\in A$$

where $V(x)$ is the value of starting at state $x$ (note that $V(x)$ is the decision variable), parameters $\alpha(x)>0$ for all $x$ which are termed state relevance weights and are typically normalized, that is $\sum_x\alpha(x)=1$ (the solution of the above LP is actually, surprisingly, independent of the exact choice of $\alpha$), $R(x,a)$ is the reward obtained in state $x$ when action $a$ is taken, and $P(x'|x,a)$ is the probability that transition to state $x'$ when we take action $a$ in state $x$.

Question: does anyone know of a similar linear programming formulation for solving partially observable Markov decision processes (POMDPs)?

Answer 1

What is known about the complexity of finding optimal policies for POMDPs indicates that solution by Linear Programming is not possible in the general case. When the decision horizon is bounded (finite), finding optimal POMDP policies is PSPACE-hard (Papadimitriou and Tsitsiklis, 1987). When the decision horizon is infinite and we are using e.g. the geometrically discounted rewards, finding optimal POMDP policies is unsolvable (Madani, Hanks, Condon 1999). Linear Programming is solvable in polynomial time, and (efficient) reductions from the above PSPACE-hard and unsolvable problems to Linear Programming therefore are not believed to exist and do not exist, respectively. Solution of POMDPs in sufficiently simple special cases is possible with LP, of course (like MDPs, which are fully observable POMDPs).