5 papers
Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives
Ali Asadi, Krishnendu Chatterjee, David Lurie +1
Partially observable Markov decision processes (POMDPs) are a central model for uncertainty in sequential decision making. The most basic objective is the reachability objective, w…
ε-Stationary Nash Equilibria in Multi-player Stochastic Graph Games
Ali Asadi, Léonard Brice, Krishnendu Chatterjee +1
A strategy profile in a multi-player game is a Nash equilibrium if no player can unilaterally deviate to achieve a strictly better payoff. A profile is an -Nash equilibrium if n…
Lower Bound on Howard Policy Iteration for Deterministic Markov Decision Processes
Ali Asadi, Krishnendu Chatterjee, Jakob de Raaij
Deterministic Markov Decision Processes (DMDPs) are a mathematical framework for decision-making where the outcomes and future possible actions are deterministically determined by…
Qualitative Analysis of -Regular Objectives on Robust MDPs
Ali Asadi, Krishnendu Chatterjee, Ehsan Kafshdar Goharshady +2
Robust Markov Decision Processes (RMDPs) generalize classical MDPs that consider uncertainties in transition probabilities by defining a set of possible transition functions. An ob…
Limit-sure reachability for small memory policies in POMDPs is NP-complete
Ali Asadi, Krishnendu Chatterjee, Raimundo Saona +1
A standard model that arises in several applications in sequential decision making is partially observable Markov decision processes (POMDPs) where a decision-making agent interact…