Mixing Probabilistic and non-Probabilistic Objectives in Markov Decision Processes
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 surely, existentially, or with non-zero probability. In this setting, relevant strategies are randomized infinite memory strategies: both infinite memory and randomization may be needed to play optimally. We provide algorithms to solve the general case of Boolean combinations and we also investigate relevant subcases. We further report on complexity bounds for these problems.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Markov Chains on Orbits of Permutation Groups
We present a novel approach to detecting and utilizing symmetries in probabilistic graphical models with two main contributions. First, we present a scalable approach to computing generating sets of permutation groups re…
Statistically Model Checking PCTL Specifications on Markov Decision Processes via Reinforcement Learning
Probabilistic Computation Tree Logic (PCTL) is frequently used to formally specify control objectives such as probabilistic reachability and safety. In this work, we focus on model checking PCTL specifications statistica…
NegationQ-Learningreinforcement-learningReinforcement Learning+1Decentralized Planning Using Probabilistic Hyperproperties
Multi-agent planning under stochastic dynamics is usually formalised using decentralized (partially observable) Markov decision processes ( MDPs) and reachability or expected reward specifications. In this paper, we prop…
Online Regularized Learning Algorithms in RKHS with $β$- and $φ$-Mixing Sequences
In this paper, we study an online regularized learning algorithm in a reproducing kernel Hilbert spaces (RKHS) based on a class of dependent processes. We choose such a process where the degree of dependence is measured …
Value Iteration with Guessing for Markov Chains and Markov Decision Processes
Two standard models for probabilistic systems are Markov chains (MCs) and Markov decision processes (MDPs). Classic objectives for such probabilistic models for control and planning problems are reachability and stochast…