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)?