Showing 2024Show all
3 papers · 1 filter
cs.CC2024
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…
cs.GT2024
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…
cs.GT2024
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…