{"id":"arxiv/2605.12191","url":"https://arxiv.org/abs/2605.12191","tags":["cs.GT","math.PR"],"score":0,"title":"Sure-almost-sure and Sure-limit-sure Window Mean Payoff in Markov Decision Processes","domain":"cs.GT","source":"arxiv","authors":["Pranshu Gaba","Shibashis Guha"],"reviews":0,"subject":"cs.GT","summary":"Given rationals $α$ and $β$, the sure-almost-sure problem for a threshold Boolean objective $\\varphi$ in a Markov decision process (MDP) asks if one can simultaneously ensure that all outcomes of the MDP have $\\varphi$-value at least $α$ (i.e. sure $α$ satisfaction) and with probability $1$ the outcome has $\\varphi$-value at least $β$ (i.e. almost-sure $β$ satisfaction). The sure-limit-sure problem asks if for all $\\varepsilon > 0$ one can simultaneously ensure that all outcomes have $\\varphi$-value at least $α$ and with probability at least $1 - \\varepsilon$ the outcome has $\\varphi$-value…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-05-12","reactions":{}}