LFCS Seminar: Tuesday 15 September: Pranshu Gaba | LFCS

Tue, 15 Sep, 4.10pm

Venue: Dugald Steward Building DS-1.20 (unusual venue)

Title: Sure-Almost-Sure Window Mean Payoff in Markov Decision Processes

Abstract: Given rationals α and β, the sure-almost-sure problem for a

quantitative objective φ in a Markov decision process (MDP) asks if one

can simultaneously ensure that all outcomes of the MDP have φ-value at

least α (i.e., sure α satisfaction), and with probability 1 the outcome

has φ-value at least β (i.e., almost-sure β satisfaction). Moreover,

if simultaneous satisfaction of objectives is possible, then one

would also like to construct a strategy that achieves this. Even if both

sure satisfaction and almost-sure satisfaction for an objective are

known, combining the two is often non-trivial and requires novel

techniques and approaches.

In this talk, we look at the sure-almost-sure problem for window

mean-payoff objectives. The window mean-payoff objective

strengthens the standard mean-payoff objective by requiring that the

average payoff from each point in the play become at least than the

threshold in at most ℓ steps. For the window mean-payoff objective, we

show that while the computational complexity of the sure-almost-sure

problem matches that of sure satisfaction and almost-sure

satisfaction, the memory requirement of winning strategies for

sure-almost-sure satisfaction is greater than that of both sure and

almost-sure satisfaction.

Link:

(CONCUR 2026)

This article was published on Monday 17 August 2026