2021/01/18 by Richard Mayr, Mayr, Richard, Sven Schewe +5
Computer Science · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Reinforcement Learning in Robotics
paper · doi:10.48550/arxiv.2101.06989
openalex publication_date 2021/01/18 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
We study stochastic games with energy-parity objectives, which combine quantitative rewards with a qualitative ω-regular condition: The maximizer aims to avoid running out of energy while simultaneously satisfying a parity condition. We show that the corresponding almost-sure problem, i.e., checking whether there exists a maximizer strategy that achieves the energy-parity objective with probability 1 when starting at a given energy level k, is decidable and in NP ∩ coNP. The same holds for checking if such a k exists and if a given k is minimal.