BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1752
DTSTAMP:20260722T065024Z
SUMMARY:The Value Problem for Multiple-Environment MDPs with Parity Objecti
 ves
DESCRIPTION:Speaker: Chandralekha P (TIFR)\n\nAbstract: \nIn a Markov decis
 ion process (MDP)\, the value of a strategy with respect to a parity objec
 tive is the probability with which the strategy satisfies the parity objec
 tive. The value of an MDP is the supremum of the values of all strategies.
  It is known that\, for MDPs with parity objectives\, both the limit-sure 
 problem (deciding whether the value is 1) and the almost-sure problem (dec
 iding whether there exists a strategy with value 1) can be solved in polyn
 omial time.\nNow\, consider multiple-environment Markov decision processes
  (MEMDPs)\, where the transition function is chosen from a finite set of e
 nvironments sharing the same state space and action set. A single strategy
  must operate correctly without knowing which environment is the actual on
 e. The value of a strategy is therefore evaluated with respect to all poss
 ible environments. I will be presenting algorithms for the almost-sure and
  limit-sure value problems for parity objectives\, showing that both probl
 ems are PSPACE-complete in general\, and discussing polynomial time algori
 thms when the number of environments is fixed.\n \nThis talk will be base
 d on the following paper: https://arxiv.org/pdf/2504.15960 by Krishnendu
  Chatterjee\, Laurent Doyen\, Jean-François Raskin\, Ocan Sankur.\n \n
URL:https://www.tcs.tifr.res.in/web/events/1752
DTSTART;TZID=Asia/Kolkata:20260729T173000
DTEND;TZID=Asia/Kolkata:20260729T183000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR