Approximating the Value of Energy-Parity Objectives in Simple Stochastic Games

Abstract

We consider simple stochastic games $\mathcal{G}$ with energy-parity objectives, a combination of quantitative rewards with a qualitative parity condition. The Maximizer tries to avoid running out of energy while simultaneously satisfying a parity condition. We present an algorithm to approximate the value of a given configuration in 2-NEXPTIME. Moreover, $\epsilon$-optimal strategies for either player require at most $O(2EXP(|\mathcal{G}|)\cdot \log (\frac{1}{\epsilon }))$ memory modes.

Full version of a paper presented at MFCS 2023