Omega-Regular Decision Processes
This work addresses the problem of representing and optimizing non-Markovian decision processes with future promises for researchers in AI and formal methods, but it is incremental as it builds on existing RDPs and MDP frameworks.
The paper tackles the limited expressiveness of regular decision processes (RDPs) by introducing omega-regular decision processes (ODPs), which extend non-Markovian aspects to omega-regular lookaheads, and reduces optimization and learning for ODPs to lexicographic methods over finite MDPs, with experimental results showing effectiveness.
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.