Low-complexity modular policies: learning to play Pac-Man and a new
  framework beyond MDPs
  In this paper we propose a method that learns to play Pac-Man. We define a
set of high-level observation and action modules. Actions are temporally
extended, and multiple action modules may be in effect concurrently. A decision
of the agent is represented as a rule-based policy. For learning, we apply the
cross-entropy method, a recent global optimization algorithm. The learned
policies reached better score than the hand-crafted policy, and neared the
score of average human players. We argue that learning is successful mainly
because (i) the policy space includes the combination of individual actions and
thus it is sufficiently rich, (ii) the search is biased towards low-complexity
policies and low complexity solutions can be found quickly if they exist. Based
on these principles, we formulate a new theoretical framework, which can be
found in the Appendix as supporting material.
