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

  • $\begingroup$ Not an answer, but one thing is that the state variable $x$ is finite in an MDP. In a POMDP, the value function depends on the belief state which lives in an infinite-dimensional space. This complicates the extension to the POMDP setting. $\endgroup$ – Erik M Jan 1 '16 at 6:26

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.