8 papers · 1 filter
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…