Omega-Regular Decision Processes
Ernst Moritz Hahn Mateo Perez Sven Schewe Fabio Somenzi Ashutosh Trivedi Dominik Wojtczak
Regular decision processes (RDPs) are a subclass of non-Markovian decision
processes where the transition and reward functions are guarded by some regular
property of the past (a lookback). While RDPs enable intuitive and succinct
representation of non-Markovian decision processes, their expressive power
coincides with finite-state Markov decision processes (MDPs). We introduce
omega-regular decision processes (ODPs) where the non-Markovian aspect of the
transition and reward functions are extended to an omega-regular lookahead over
the system evolution. Semantically, these lookaheads can be considered as
promises made by the decision maker or the learning agent about her future
behavior. In particular, we assume that, if the promised lookaheads are not
met, then the payoff to the decision maker is $\bot$ (least desirable payoff),
overriding any rewards collected by the decision maker. We enable optimization
and learning for ODPs under the discounted-reward objective by reducing them to
lexicographic optimization and learning over finite MDPs. We present
experimental results demonstrating the effectiveness of the proposed reduction.