Omega-regular Decision Processes

Abstract

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

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyhahn2023omega

Related papers

• Regular Decision Processes For Grid Worlds (2021)0.00
• Efficient PAC Reinforcement Learning In Regular Decision Processes (2021)2.26
• OCMDP: Observation-constrained Markov Decision Process (2024)0.00
• Twice Regularized Markov Decision Processes: The Equivalence Between Robustness And Regularization (2023)0.00
• A PAC Learning Algorithm For LTL And Omega-regular Objectives In Mdps (2023)3.58
• Double Reinforcement Learning For Efficient Off-policy Evaluation In Markov Decision Processes (2019)0.00
• Twice Regularized Mdps And The Equivalence Between Robustness And Regularization (2021)0.00
• Robust Anytime Learning Of Markov Decision Processes (2022)0.00