Regular Decision Processes: A Model for Non-Markovian Domains

Regular Decision Processes: A Model for Non-Markovian Domains

Ronen I. Brafman, Giuseppe De Giacomo

Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence
Main track. Pages 5516-5522. https://doi.org/10.24963/ijcai.2019/766

We introduce and study Regular Decision Processes (RDPs), a new, compact, factored model for domains with non-Markovian dynamics and rewards. In RDPs, transition and reward functions are specified using formulas in linear dynamic logic over finite traces, a language with the expressive power of regular expressions. This allows specifying complex dependence on the past using intuitive and compact formulas, and provides a model that generalizes MDPs and k-order MDPs. RDPs can also approximate POMDPs without having to postulate the existence of hidden variables, and, in principle, can be learned from observations only. 
Keywords:
Planning and Scheduling: Markov Decisions Processes
Planning and Scheduling: POMDPs
Planning and Scheduling: Other approaches to planning
Planning and Scheduling: Planning under Uncertainty