Events and news relevant to the Laboratory for Foundations of Computer Science

[Ohad Kammar <ohad.kammar@ed.ac.uk>]

Hi,

Today we'll have the second LFCS seminar for this week:

2. Tuesday, 15 Sep, 4.10pm (usual day)

  Pranshu Gaba, Tata Institute of Fundamental Research, Mumbai

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

  The seminars will take place in-person only.

We're synchronising the seminar time with the teaching timetable, and

plan to start the talk at the advertised time, so please arrive a minute or two

earlier.

In detail:

----------------------------------------------------------------------

Pranshu Gaba, Tata Institute of Fundamental Research, Mumbai

https://pranshugaba.com/

  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:

https://arxiv.org/abs/2605.12191

(CONCUR 2026)

----------------------------------------------------------------------

Upcoming seminars:

------------------

22 Sep: Sabine Oechsner, Vrije Universiteit Amsterdam

If you would like to propose a speaker, or speak yourself, please contact me.

The seminar webpages:

http://web.inf.ed.ac.uk/lfcs/events/lfcs-seminars

Yours,

Ohad.

The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. Is e buidheann carthannais a th’ ann an Oilthigh Dhùn Èideann, clàraichte an Alba, àireamh clàraidh SC005336.