15 papers
Algorithms with Smoothed Polynomial-Time Complexity for Deterministic Discounted-sum and Mean-payoff Games
Ali Asadi, Krishnendu Chatterjee, Ruichen Luo
Turn-based deterministic games on graphs are two-player zero-sum games played on finite directed graphs, where the vertex set is partitioned between the Max and the adversarial Min…
Values of Absorbing Recursive Games Express All Real Algebraic Numbers
Ali Asadi, Krishnendu Chatterjee
Many classes of two-player zero-sum stochastic games have the orderfield property: if all payoffs and transition probabilities lie in a subfield of , so does the undisc…
The Complexity of Approximating the Value in Revealing POMDPs with Long-Run Average Objectives
Ali Asadi, Krishnendu Chatterjee, David Lurie
We study partially observable Markov decision processes (POMDPs) with long-run average objectives, where the payoff is defined as the limit inferior of the expected average rewards…
Quantitative Analysis of -Regular Robust MDPs
Ali Asadi, Krishnendu Chatterjee, Ehsan Kafshdar Goharshady +3
Robust Markov Decision Processes (RMDPs) generalize classical MDPs by allowing uncertainty in transition probabilities and optimizing against their worst-case realization. We consi…
PAC Learning in Turn-Based Stochastic Games with Reachability Objectives: A Decentralized Private Approach via Expected Conditional Distance
Ali Asadi, Krishnendu Chatterjee, Pavol Kebis
Reachability is the most fundamental logical objective, yet it is notoriously difficult to learn in reinforcement learning settings: even for Markov decision processes, PAC learnin…
Generalized Bidding Games: Where Bidding and Stochastic Games Meet
Ali Asadi, Thomas A. Henzinger, Ehsan Kafshdar Goharshady +2
Two-player games on graphs are a classical framework for analyzing strategic decision making. In turn-based games, two players move a token along the edges of the graph, and the ri…
On the Complexity of Discounted Robust MDPs with Uncertainty Sets
Ali Asadi, Krishnendu Chatterjee, Alipasha Montaseri +1
A basic model in sequential decision making is the Markov decision process (MDP), which is extended to Robust MDPs (RMDPs) by allowing uncertainty in transition probabilities and o…
Strongly Polynomial Time Complexity of Policy Iteration for Robust MDPs
Ali Asadi, Krishnendu Chatterjee, Ehsan Goharshady +3
Markov decision processes (MDPs) are a fundamental model in sequential decision making. Robust MDPs (RMDPs) extend this framework by allowing uncertainty in transition probabilitie…
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…
Deterministic Sub-exponential Algorithm for Discounted-sum Games with Unary Weights
Ali Asadi, Krishnendu Chatterjee, Raimundo Saona +1
Turn-based discounted-sum games are two-player zero-sum games played on finite directed graphs. The vertices of the graph are partitioned between player 1 and player 2. Plays are i…
Concurrent Stochastic Games with Stateful-discounted and Parity Objectives: Complexity and Algorithms
Ali Asadi, Krishnendu Chatterjee, Raimundo Saona +1
We study two-player zero-sum concurrent stochastic games with finite state and action space played for an infinite number of steps. In every step, the two players simultaneously an…