4 citations · 5 across the 12 of their papers we have counts for
14 papers
Approximating the Uniform Value in Hidden Stochastic Games with Doeblin Condition
Krishnendu Chatterjee, David Lurie, Raimundo Saona +1
We study \emph{zero-sum two-player hidden stochastic games}, where players receive partial observations of the state. We focus on a central solution concept for analyzing long-dura…
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…
Value Iteration with Guessing for Markov Chains and Markov Decision Processes
Krishnendu Chatterjee, Mahdi JafariRaviz, Raimundo Saona +1
Two standard models for probabilistic systems are Markov chains (MCs) and Markov decision processes (MDPs). Classic objectives for such probabilistic models for control and plannin…
Linear Equations with Min and Max Operators: Computational Complexity
Krishnendu Chatterjee, Ruichen Luo, Raimundo Saona +1
We consider a class of optimization problems defined by a system of linear equations with min and max operators. This class of optimization problems has been studied under restrict…
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…
IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates
Giordano Giambartolomei, Frederik Mallmann-Trenn, Raimundo Saona
Prophet inequalities are a central object of study in optimal stopping theory. In the iid model, a gambler sees values in an online fashion, sampled independently from a given dist…
Stochastic Homogenization of HJ Equations: a Differential Game Approach
Andrea Davini, Raimundo Saona, Bruno Ziliotto
We prove stochastic homogenization for a class of non-convex and non-coercive first-order Hamilton-Jacobi equations in a finite-range-dependence environment for Hamiltonians that c…
Uniform Value and Decidability in Ergodic Blind Stochastic Games
Krishnendu Chatterjee, David Lurie, Raimundo Saona +1
We study a class of two-player zero-sum stochastic games known as \textit{blind stochastic games}, where players neither observe the state nor receive any information about it duri…
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…
Zero-sum Random Games on Directed Graphs
Luc Attia, Lyuben Lichev, Dieter Mitsche +2
This paper considers a class of two-player zero-sum games on directed graphs whose vertices are equipped with random payoffs of bounded support known by both players. Starting from…
Prophet Inequalities: Separating Random Order from Order Selection
Giordano Giambartolomei, Frederik Mallmann-Trenn, Raimundo Saona
Prophet inequalities are a central object of study in optimal stopping theory. A gambler is sent values in an online fashion, sampled from an instance of independent distributions,…
Repeated Prophet Inequality with Near-optimal Bounds
Krishnendu Chatterjee, Mona Mohammadi, Raimundo Saona
In modern sample-driven Prophet Inequality, an adversary chooses a sequence of items with values to be presented to a decision maker (DM). The process f…
Finite-Memory Strategies in POMDPs with Long-Run Average Objectives
Krishnendu Chatterjee, Raimundo Saona, Bruno Ziliotto
Partially observable Markov decision processes (POMDPs) are standard models for dynamic systems with probabilistic and nondeterministic behaviour in uncertain environments. We prov…
Prophet Secretary Through Blind Strategies
Jose Correa, Raimundo Saona, Bruno Ziliotto
In the classic prophet inequality, samples from independent random variables arrive online. A gambler that knows the distributions must decide at each point in time whether to stop…