From the 1 of 9 linked papers with an AI index.
9 papers
PAC Learning in Turn-Based Stochastic Games with Reachability Objectives: A Decentralized Private Approach via Expected Conditional Distance
Ali Asadi, Krishnendu Chatterjee, Pavol Kebis
The paper studies PAC learning for reachability objectives in turn‑based stochastic games, proposing a decentralized approach where each player learns privately without sharing alg…
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…
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…
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…
ε-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…
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…