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