# Orderability of Belief States in a POMDP?

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?

• Can you define what is POMDP? what do you refer with "optimal policy"? – jonaprieto Apr 25 '16 at 15:51

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$.
• 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! – jonem May 3 '16 at 20:59
• Oops, I meant if $g(a)$ takes the system to a better belief than $g(b)$, then $g(a)\ge g(b)$ – jonem May 3 '16 at 21:43
• 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'$. – jonem May 7 '16 at 2:33