  Markov Decision Processes (Mdps) form a versatile framework used to model a
wide range of optimization problems. The Mdp model consists of sets of states,
actions, time steps, rewards, and probability transitions. When in a given
state and at a given time, the decision maker's action generates a reward and
determines the state at the next time step according to the probability
transition function. However, Mdps assume that the decision maker knows the
state of the controlled dynamical system. Hence, when one needs to optimize
controlled dynamical systems under partial observation, one often turns toward
the formalism of Partially Observed Markov Decision Processes (Pomdp). Pomdps
are often untractable in the general case as Dynamic Programming suffers from
the curse of dimensionality. Instead of focusing on the general Pomdps, we
present a subclass where transitions and observations mappings are
deterministic: Deterministic Partially Observed Markov Decision Processes
(Det-Pomdp). That subclass of problems has been studied by (Littman, 1996) and
(Bonet, 2009). It was first considered as a limit case of Pomdps by Littman,
mainly used to illustrate the complexity of Pomdps when considering as few
sources of uncertainties as possible. In this paper, we improve on Littman's
complexity bounds. We then introduce and study an even simpler class: Separated
Det-Pomdps and give some new complexity bounds for this class. This new class
of problems uses a property of the dynamics and observation to push back the
curse of dimensionality.
