4 citations · 5 across the 12 of their papers we have counts for
7 papers · 1 filter
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…