Tata Institute of Fundamental Research
The Value Problem for Multiple-Environment MDPs with Parity Objectives
Oral Qualifier
Speaker:
Chandralekha P (TIFR)
Organiser:
Shibashis Guha
Date:
Wednesday, 29 Jul 2026, 17:30 to 18:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
In a Markov decision process (MDP), the value of a strategy with respect to a parity objective is the probability with which the strategy satisfies the parity objective. 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 (deciding whether there exists a strategy with value 1) can be solved in polynomial time.
Now, consider multiple-environment Markov decision processes (MEMDPs), where the transition function is chosen from a finite set of environments sharing the same state space and action set. A single strategy must operate correctly without knowing which environment is the actual one. The value of a strategy is therefore evaluated with respect to all possible environments. I will be presenting algorithms for the almost-sure and limit-sure value problems for parity objectives, showing that both problems are PSPACE-complete in general, and discussing polynomial time algorithms when the number of environments is fixed.
This talk will be based on the following paper: https://arxiv.org/pdf/2504.15960 by Krishnendu Chatterjee, Laurent Doyen, Jean-François Raskin, Ocan Sankur.
| Speaker: | Chandralekha P (TIFR) |
| Organiser: | Shibashis Guha |
| Date: | Wednesday, 29 Jul 2026, 17:30 to 18:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
In a Markov decision process (MDP), the value of a strategy with respect to a parity objective is the probability with which the strategy satisfies the parity objective. 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 (deciding whether there exists a strategy with value 1) can be solved in polynomial time.
Now, consider multiple-environment Markov decision processes (MEMDPs), where the transition function is chosen from a finite set of environments sharing the same state space and action set. A single strategy must operate correctly without knowing which environment is the actual one. The value of a strategy is therefore evaluated with respect to all possible environments. I will be presenting algorithms for the almost-sure and limit-sure value problems for parity objectives, showing that both problems are PSPACE-complete in general, and discussing polynomial time algorithms when the number of environments is fixed.
This talk will be based on the following paper: https://arxiv.org/pdf/2504.15960 by Krishnendu Chatterjee, Laurent Doyen, Jean-François Raskin, Ocan Sankur.