Abstract
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
