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

2023/07/11 by Dantam, Mohan, Mayr, Richard
#91A15 #91A35 #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Mathematics #G.3 #Probability (math.PR)

paper · doi:10.48550/arxiv.2307.05762

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, ε-optimal strategies for either player require at most O(2EXP(|\mathcal G|)⋅log((1)/(ε))) memory modes.

Related

• Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP
• Energy Parity Games
• Energy and Mean-Payoff Parity Markov Decision Processes
• Strategy Synthesis for Multi-dimensional Quantitative Objectives
• Bounding Average-energy Games