  Planning and learning in Partially Observable MDPs (POMDPs) are among the
most challenging tasks in both the AI and Operation Research communities.
Although solutions to these problems are intractable in general, there might be
special cases, such as structured POMDPs, which can be solved efficiently. A
natural and possibly efficient way to represent a POMDP is through the
predictive state representation (PSR) - a representation which recently has
been receiving increasing attention. In this work, we relate POMDPs to
multiplicity automata- showing that POMDPs can be represented by multiplicity
automata with no increase in the representation size. Furthermore, we show that
the size of the multiplicity automaton is equal to the rank of the predictive
state representation. Therefore, we relate both the predictive state
representation and POMDPs to the well-founded multiplicity automata literature.
Based on the multiplicity automata representation, we provide a planning
algorithm which is exponential only in the multiplicity automata rank rather
than the number of states of the POMDP. As a result, whenever the predictive
state representation is logarithmic in the standard POMDP representation, our
planning algorithm is efficient.
