# Omega-Regular Decision Processes

arXiv: https://arxiv.org/abs/2312.08602 · HTML: https://mlsanity.com/paper/2312.08602/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 38 references that are in the map.
- First posted on arXiv 14 Dec 2023.

## Builds on (most cited first, 11 of 11)

- [Concrete Problems in AI Safety](https://mlsanity.com/paper/1606.06565/) (2016)
- [The Effects of Reward Misspecification: Mapping and Mitigating Misaligned Models](https://mlsanity.com/paper/2201.03544/) (2022)
- [Reward Machines: Exploiting Reward Function Structure in Reinforcement Learning](https://mlsanity.com/paper/2010.03950/) (2020)
- [Chip Placement with Deep Reinforcement Learning](https://mlsanity.com/paper/2004.10746/) (2020)
- [Omega-Regular Objectives in Model-Free Reinforcement Learning](https://mlsanity.com/paper/1810.00950/) (2018)
- [Control Synthesis from Linear Temporal Logic Specifications using Model-Free Reinforcement Learning](https://mlsanity.com/paper/1909.07299/) (2019)
- [Probably Approximately Correct MDP Learning and Control With Temporal Logic Constraints](https://mlsanity.com/paper/1404.7073/) (2014)
- [A Learning Based Approach to Control Synthesis of Markov Decision Processes for Linear Temporal Logic Specifications](https://mlsanity.com/paper/1409.5486/) (2014)
- [Model-Free Learning of Safe yet Effective Controllers](https://mlsanity.com/paper/2103.14600/) (2021)
- [Maximum Realizability for Linear Temporal Logic Specifications](https://mlsanity.com/paper/1804.00415/) (2018)
- [On Good-for-MDPs Automata](https://mlsanity.com/paper/2202.07629/) (2022)

## Abstract (arXiv)

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.