Omega-Regular Decision Processes

2023-12-14 · 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.

📄 PDF Abstract BibTeX arXiv:2312.08602

Code (0)

등록된 구현이 없습니다.

A PAC Learning Algorithm for LTL and Omega-regular Objectives in MDPs

2023-10-18 · Mateo Perez, Fabio Somenzi, Ashutosh Trivedi

Linear temporal logic (LTL) and omega-regular objectives -- a superset of LTL -- have seen recent use as a way to express non-Markovian objectives in reinforcement learning. We introduce a model-based probably approximat…

PAC learning reinforcement-learning

Reinforcement Learning for Omega-Regular Specifications on Continuous-Time MDP

2023-03-16 · Amin Falah, Shibashis Guha, Ashutosh Trivedi

Continuous-time Markov decision processes (CTMDPs) are canonical models to express sequential decision-making under dense-time and stochastic environments. When the stochastic evolution of the environment is only availab…

Decision Making reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+2

Omega-Regular Objectives in Model-Free Reinforcement Learning

2018-09-26 · Hahn Ernst Moritz, Perez Mateo, Schewe Sven, Somenzi Fabio 외

We provide the first solution for model-free reinforcement learning of {\omega}-regular objectives for Markov decision processes (MDPs). We present a constructive reduction from the almost-sure satisfaction of {\omega}-r…

model reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives

2024-12-16 · Marius Belly, Nathanaël Fijalkow, Hugo Gimbert, Florian Horn 외

Partially observable Markov decision processes (POMDPs) form a prominent model for uncertainty in sequential decision making. We are interested in constructing algorithms with theoretical guarantees to determine whether …

Decision Making Sequential Decision Making

Mixing Probabilistic and non-Probabilistic Objectives in Markov Decision Processes

2020-04-28 · Raphaël Berthon, Shibashis Guha, Jean-François Raskin

In this paper, we consider algorithms to decide the existence of strategies in MDPs for Boolean combinations of objectives. These objectives are omega-regular properties that need to be enforced either surely, almost sur…