  Recently regular decision processes have been proposed as a well-behaved form
of non-Markov decision process. Regular decision processes are characterised by
a transition function and a reward function that depend on the whole history,
though regularly (as in regular languages). In practice both the transition and
the reward functions can be seen as finite transducers. We study reinforcement
learning in regular decision processes. Our main contribution is to show that a
near-optimal policy can be PAC-learned in polynomial time in a set of
parameters that describe the underlying decision process. We argue that the
identified set of parameters is minimal and it reasonably captures the
difficulty of a regular decision process.
