10 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…
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…
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…
Risk-aware Markov Decision Processes Using Cumulative Prospect Theory
Thomas Brihaye, Krishnendu Chatterjee, Stefanie Mohr +1
Cumulative prospect theory (CPT) is the first theory for decision-making under uncertainty that combines full theoretical soundness and empirically realistic features [P.P. Wakker…
The role of behavioural plasticity in finite vs infinite populations
M. Kleshnina, K. Kaveh, K. Chatterjee
Evolutionary game theory has proven to be an elegant framework providing many fruitful insights in population dynamics and human behaviour. Here, we focus on the aspect of behaviou…