Consider a POMDP with integer states $1,2,\ldots,N$, where $N$ is finite. We thus have a complete order over the states.

It seems reasonable to think that belief states for this POMDP may be orderable in some partial order sense.

Does this orderability translate into any structure of the optimal policy? Anyone have any relevant literature?

  • $\begingroup$ Can you define what is POMDP? what do you refer with "optimal policy"? $\endgroup$ Apr 25, 2016 at 15:51

1 Answer 1


Having recently worked on this topic, I can say that the answer to both of your questions is yes.

The belief states may be partially ordered for example applying the monotone likelihood ratio, or other appropriate stochastic orderings that tell when a probability mass function (pmf) $f$ -- here a belief state -- is "greater than" another pmf $g$.

Roughly speaking, if the POMDP state transition and observation models are such that the partial order is preserved on a belief update operation, structural statements about the optimal policy of the POMDP can be made. Details may be found in a recent journal paper: V. Krishnamurthy, U. Pareek, Myopic Bounds for Optimal Policies of POMDPs: An extension of Lovejoy’s Structural Results, Operations Research, 2014; available at the author's website. The article also provides a literature review on the topic where further references may be found.

Krishnamurthy and collaborators also have a paper where the MLR ordering is applied on a single line in the belief space, on which the MLR order applies to every belief state: V. Krishnamurthy, D. Djonin, Structured Threshold Policies for Dynamic Sensor Scheduling--A POMDP Approach, IEEE Trans Signal Processing, Vol.55, No.10, pp.4938--4957.

  • $\begingroup$ Thank you for your informative reply! So, for two beliefs, say a and b, where $a\ge_{r} b$ in the MLR sense, we can say under some conditions that the policy obeys $g(a)\ge g(b)$, where $g()$ is the policy. What is the order for the actions, that is, how is $g(a)$ greater than $g(b)$? Is this a partial order? I'm thinking that it has something to do with comparing the outcomes of the actions, that is, if $a$ takes the system to a better belief (in the MLR sense) than $b$, then $a\ge b$? I'm not sure, though. Nevermind: it seems this was addressed in the paper! $\endgroup$
    – jonem
    May 3, 2016 at 20:59
  • $\begingroup$ Oops, I meant if $g(a)$ takes the system to a better belief than $g(b)$, then $g(a)\ge g(b)$ $\endgroup$
    – jonem
    May 3, 2016 at 21:43
  • $\begingroup$ I have a question: are there results using the MLR order for when the state-space is partially ordered? That is, not linearly ordered. There may exist states $s$ and $s'$ such that $s$ is not comparable to $s'$. $\endgroup$
    – jonem
    May 7, 2016 at 2:33
  • $\begingroup$ @jonem glad to see you found an answer to the first question! I'm not aware of any such work with partially ordered state space. However, I added a note about another paper that applies MLR ordering along a single line in the belief simplex. Maybe it could be possible to choose the line in a way that corresponds to some partial order requirement. But this is getting more hypothetical than an actual answer :) Is this a research problem you are working on? $\endgroup$
    – mikkola
    May 9, 2016 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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