Markov Abstractions for PAC Reinforcement Learning in Non-Markov Decision Processes. (arXiv:2205.01053v2 [cs.LG] UPDATED)

Our work aims at developing reinforcement learning algorithms that do not
rely on the Markov assumption. We consider the class of Non-Markov Decision
Processes where histories can be abstracted into a finite set of states while
preserving the dynamics. We call it a Markov abstraction since it induces a
Markov Decision Process over a set of states that encode the non-Markov
dynamics. This phenomenon underlies the recently introduced Regular Decision
Processes (as well as POMDPs where only a finite number …

arxiv decision learning markov processes reinforcement reinforcement learning