Sure-almost-sure and Sure-limit-sure Window Mean Payoff in Markov Decision Processes

Pranshu Gaba, Shibashis Guha

Given rationals $\alpha$ and $\beta$, the sure-almost-sure problem for a threshold Boolean objective $\phi$ in a Markov decision process (MDP) asks if one can simultaneously ensure that all ou…