@inproceedings{21722, abstract = {Partially observable Markov decision processes (POMDPs) are a central model for uncertainty in sequential decision making. The most basic objective is the reachability objective, where a target set must be eventually visited, and the more general parity objectives can model all omega-regular specifications. For such objectives, the computational analysis problems are the following: (a) qualitative analysis that asks whether the objective can be satisfied with probability 1 (almost-sure winning) or probability arbitrarily close to 1 (limit-sure winning); and (b) quantitative analysis that asks for the approximation of the optimal probability of satisfying the objective. For general POMDPs, almost-sure analysis for reachability objectives is EXPTIME-complete, but limit-sure and quantitative analyses for reachability objectives are undecidable; almost-sure, limit-sure, and quantitative analyses for parity objectives are all undecidable. A special class of POMDPs, called revealing POMDPs, has been studied recently in several works, and for this subclass the almost-sure analysis for parity objectives was shown to be EXPTIME-complete. In this work, we show that for revealing POMDPs the limit-sure analysis for parity objectives is EXPTIME-complete, and even the quantitative analysis for parity objectives can be achieved in EXPTIME.}, author = {Asadi, Ali and Chatterjee, Krishnendu and Lurie, David and Saona Urmeneta, Raimundo J}, booktitle = {Proceedings of the AAAI Conference on Artificial Intelligence}, issn = {2374-3468}, location = {Singapore, Singapore}, number = {43}, pages = {36146--36154}, publisher = {Association for the Advancement of Artificial Intelligence}, title = {{Revealing POMDPs: Qualitative and quantitative analysis for parity objectives}}, doi = {10.1609/aaai.v40i43.40932}, volume = {40}, year = {2026}, } @inproceedings{21320, abstract = {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 distribution. Upon observing each value, the gambler either accepts it as a reward, or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is to maximise the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations. This model has been studied with infinite, finite and unknown number of values. When the gambler faces a random number of values, the model is said to have a random horizon. We consider the model in which the gambler is given a priori knowledge of the horizon’s distribution. Alijani et al. (2020) designed a single-threshold algorithm achieving a ratio of 1/2 when the random horizon has an increasing hazard rate and is independent of the values. We prove that with a single threshold, a ratio of 1/2 is actually achievable for several larger classes of horizon distributions, with the largest being known as the 𝒢 class in reliability theory. Moreover, we show that this does not extend to its dual, the ̅𝒢 class (which includes the decreasing hazard rate class), while it can be extended to low-variance horizons. Finally, we construct the first example of a family of horizons, for which multiple thresholds are necessary to achieve a nonzero ratio. We establish that the Secretary Problem optimal stopping rule provides one such algorithm, paving the way towards the study of the model beyond single-threshold algorithms.}, author = {Giambartolomei, Giordano and Mallmann-Trenn, Frederik and Saona Urmeneta, Raimundo J}, booktitle = {52nd International Colloquium on Automata, Languages, and Programming}, isbn = {9783959773720}, location = {Aarhus, Denmark}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{IID prophet inequality with random horizon: Going beyond increasing hazard rates}}, doi = {10.4230/LIPIcs.ICALP.2025.87}, volume = {334}, year = {2025}, } @article{19508, abstract = {We consider random two-player zero-sum dynamic games with perfect information on a class of infinite directed graphs. Starting from a fixed vertex, the players take turns to move a token along the edges of the graph. Every vertex is assigned a payoff known in advance by both players. Every time the token visits a vertex, Player 2 pays Player 1 the corresponding payoff. We consider a distribution over such games by assigning i.i.d. payoffs to the vertices. On the one hand, for acyclic directed graphs of bounded degree and sub-exponential expansion, we show that, when the duration of the game tends to infinity, the value converges almost surely to a constant at an exponential rate dominated in terms of the expansion. On the other hand, for the infinite d-ary tree (that does not fall into the previous class of graphs), we show convergence at a double-exponential rate.}, author = {Attia, Luc and Lichev, Lyuben and Mitsche, Dieter and Saona Urmeneta, Raimundo J and Ziliotto, Bruno}, issn = {2153-0793}, journal = {Dynamic Games and Applications}, pages = {1517--1535}, publisher = {Springer Nature}, title = {{Random zero-sum dynamic games on infinite directed graphs}}, doi = {10.1007/s13235-025-00636-4}, volume = {15}, year = {2025}, } @inproceedings{19669, abstract = {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 restrictive conditions, such as, (C1) the halting or stability condition; (C2) the non-negative coefficients condition; (C3) the sum upto 1 condition; and (C4) the only min or only max operator condition. Several seminal results in the literature focus on special cases. For example, turn-based stochastic games correspond to conditions C2 and C3; and Markov decision process to conditions C2, C3, and C4. However, the systematic computational complexity study of all the cases has not been explored, which we address in this work. Some highlights of our results are: with conditions C2 and C4, and with conditions C3 and C4, the problem is NP-complete, whereas with condition C1 only, the problem is in UP intersects coUP. Finally, we establish the computational complexity of the decision problem of checking the respective conditions.}, author = {Chatterjee, Krishnendu and Luo, Ruichen and Saona Urmeneta, Raimundo J and Svoboda, Jakub}, booktitle = {Proceedings of the 39th AAAI Conference on Artificial Intelligence}, issn = {2374-3468}, location = {Philadelphia, PA, United States}, number = {11}, pages = {11150--11157}, publisher = {Association for the Advancement of Artificial Intelligence}, title = {{Linear equations with min and max operators: Computational complexity}}, doi = {10.1609/aaai.v39i11.33212}, volume = {39}, year = {2025}, } @inproceedings{19740, abstract = {Two standard models for probabilistic systems are Markov chains (MCs) and Markov decision processes (MDPs). Classic objectives for such probabilistic models for control and planning problems are reachability and stochastic shortest path. The widely studied algorithmic approach for these problems is the Value Iteration (VI) algorithm which iteratively applies local updates called Bellman updates. There are many practical approaches for VI in the literature but they all require exponentially many Bellman updates for MCs in the worst case. A preprocessing step is an algorithm that is discrete, graph-theoretical, and requires linear space. An important open question is whether, after a polynomial-time preprocessing, VI can be achieved with sub-exponentially many Bellman updates. In this work, we present a new approach for VI based on guessing values. Our theoretical contributions are twofold. First, for MCs, we present an almost-linear-time preprocessing algorithm after which, along with guessing values, VI requires only subexponentially many Bellman updates. Second, we present an improved analysis of the speed of convergence of VI for MDPs. Finally, we present a practical algorithm for MDPs based on our new approach. Experimental results show that our approach provides a considerable improvement over existing VI-based approaches on several benchmark examples from the literature.}, author = {Chatterjee, Krishnendu and Jafariraviz, Mahdi and Saona Urmeneta, Raimundo J and Svoboda, Jakub}, booktitle = {31st International Conference on Tools and Algorithms for the Construction and Analysis of Systems}, isbn = {9783031906527}, issn = {1611-3349}, location = {Hamilton, ON, Canada}, pages = {217--236}, publisher = {Springer Nature}, title = {{Value iteration with guessing for Markov chains and Markov decision processes}}, doi = {10.1007/978-3-031-90653-4_11}, volume = {15697}, year = {2025}, } @inproceedings{20297, abstract = {A standard model that arises in several applications in sequential decision-making is partially observable Markov decision processes (POMDPs) where a decision-making agent interacts with an uncertain environment. A basic objective in POMDPs is the reachability objective, where given a target set of states, the goal is to eventually arrive at one of them. The limit-sure problem asks whether reachability can be ensured with probability arbitrarily close to 1. In general, the limit-sure reachability problem for POMDPs is undecidable. However, in many practical cases, the most relevant question is the existence of policies with a small amount of memory. In this work, we study the limit-sure reachability problem for POMDPs with a fixed amount of memory. We establish that the computational complexity of the problem is NP-complete.}, author = {Asadi, Ali and Chatterjee, Krishnendu and Saona Urmeneta, Raimundo J and Shafiee, Ali}, booktitle = {The 41st Conference on Uncertainty in Artificial Intelligence}, issn = {2640-3498}, location = {Rio de Janeiro, Brazil}, pages = {238--247}, publisher = {ML Research Press}, title = {{Limit-sure reachability for small memory policies in POMDPs is NP-complete}}, volume = {286}, year = {2025}, } @phdthesis{20234, abstract = {Game Theory is the mathematical formalization of social dynamics - systems where agents interact over time and the evolution of the state of the system depends on the decisions of every player. This thesis takes the perspective of a single player and focuses on what they can guarantee in the worst case over the behavior of other players. In other words, we consider that the objective of every other player in the game is exactly the opposite to the player. We focus on sustained interactions over time, where the players repeatedly obtain quantitative rewards over time, and they are interested in maximizing their long-term performance. Formally, this thesis focuses on zero-sum games with the liminf average objective. Two fundamental questions that Game Theory aims to answer are the following. 1. How much can a player guarantee to obtain after the interaction? 2. How to act in order to obtain the previously mentioned guarantee? These questions are formalized by the concepts of "value" and "optimal strategies". We study their properties on games that exhibit one or more of the following properties. 1. Partial Observation: the players can not perfectly observe the current state of the system during the game. We consider the model of (finite) Partially Observable Markov Decision Processes and prove that finite-memory strategies are sufficient to approximately guarantee the value. 2. Perturbed Description: the formal description of the game is perturbed by a small parameter. We consider the model of (finite) Perturbed Matrix Games, and provide algorithms to check various robustness properties and to compute the parameterized value and optimal strategies. 3. Stochastic Transitions: the actions of the players determine the behavior of the evolution of the system, described as a probability distribution over the next state. We consider the model of (finite) Perturbed Stochastic Games and provide formulas for the marginal value. 4. Infinite States: the system can be in infinitely many states. We consider the model of Random Dynamic Games on a class of infinite graphs, prove the existence of the value, and quantify the concentration of finite-horizon values.}, author = {Saona Urmeneta, Raimundo J}, issn = {2663-337X}, pages = {125}, publisher = {Institute of Science and Technology Austria}, title = {{Robustness of solutions in game theory : Values and strategies in partially observable, perturbed, stochastic, and infinite games}}, doi = {10.15479/AT-ISTA-20234}, year = {2025}, } @article{17037, abstract = {Zero-sum stochastic games are parameterized by payoffs, transitions, and possibly a discount rate. In this article, we study how the main solution concepts, the discounted and undiscounted values, vary when these parameters are perturbed. We focus on the marginal values, introduced by Mills in 1956 in the context of matrix games—that is, the directional derivatives of the value along any fixed perturbation. We provide a formula for the marginal values of a discounted stochastic game. Further, under mild assumptions on the perturbation, we provide a formula for their limit as the discount rate vanishes and for the marginal values of an undiscounted stochastic game. We also show, via an example, that the two latter differ in general.}, author = {Attia, Luc and Oliu-Barton, Miquel and Saona Urmeneta, Raimundo J}, issn = {1526-5471}, journal = {Mathematics of Operations Research}, number = {1}, pages = {482--505}, publisher = {Institute for Operations Research and the Management Sciences}, title = {{Marginal values of a stochastic game}}, doi = {10.1287/moor.2023.0297}, volume = {50}, year = {2025}, } @inproceedings{17098, abstract = {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 infinite walks on the graph where the next vertex is decided by a player that owns the current vertex. Each edge is assigned an integer weight and the payoff of a play is the discounted-sum of the weights of the play. The goal of player 1 is to maximize the discounted-sum payoff against the adversarial player 2. These games lie in NP ∩ coNP and are among the rare combinatorial problems that belong to this complexity class and the existence of a polynomial-time algorithm is a major open question. Since breaking the general exponential barrier has been a challenging problem, faster parameterized algorithms have been considered. If the discount factor is expressed in unary, then discounted-sum games can be solved in polynomial time. However, if the discount factor is arbitrary (or expressed in binary), but the weights are in unary, none of the existing approaches yield a sub-exponential bound. Our main result is a new analysis technique for a classical algorithm (namely, the strategy iteration algorithm) that present a new runtime bound which is [EQUATION] for game graphs with n vertices and absolute weights of at most W. In particular, our result yields a deterministic sub-exponential bound for games with weights that are constant or represented in unary.}, author = {Asadi, Ali and Chatterjee, Krishnendu and Svoboda, Jakub and Saona Urmeneta, Raimundo J}, booktitle = {39th Annual ACM/IEEE Symposium on Logic in Computer Science}, isbn = {9798400706608}, issn = {1043-6871}, location = {Tallinn, Estonia}, publisher = {Association for Computing Machinery}, title = {{Deterministic sub-exponential algorithm for discounted-sum games with unary weights}}, doi = {10.1145/3661814.3662080}, year = {2024}, } @inproceedings{17099, abstract = {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 and independently choose an action. Given the current state and the chosen actions, the next state is obtained according to a stochastic transition function. An objective is a measurable function on plays (or infinite trajectories) of the game, and the value for an objective is the maximal expectation that the player can guarantee against the adversarial player. We consider: (a) stateful-discounted objectives, which are similar to the classical discounted-sum objectives, but states are associated with different discount factors rather than a single discount factor; and (b) parity objectives, which are a canonical representation for ω-regular objectives. For stateful-discounted objectives, given an ordering of the discount factors, the limit value is the limit of the value of the stateful-discounted objectives, as the discount factors approach zero according to the given order. The computational problem we consider is the approximation of the value within an arbitrary additive error. The above problem is known to be in EXPSPACE for the limit value of statefuldiscounted objectives and in PSPACE for parity objectives. The best-known algorithms for both the above problems are at least exponential time, with an exponential dependence on the number of states and actions. Our main results for the value approximation problem for the limit value of stateful-discounted objectives and parity objectives are as follows: (a) we establish TFNP[NP] complexity; and (b) we present algorithms that improve the dependency on the number of actions in the exponent from linear to logarithmic. In particular, if the number of states is constant, our algorithms run in polynomial time.}, author = {Asadi, Ali and Chatterjee, Krishnendu and Saona Urmeneta, Raimundo J and Svoboda, Jakub}, booktitle = {44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science}, isbn = {9783959773553}, issn = {1868-8969}, location = {Gujarat, India}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms}}, doi = {10.4230/LIPIcs.FSTTCS.2024.5}, volume = {323}, year = {2024}, } @unpublished{17101, abstract = {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 a fixed vertex, players take turns to move a token along the edges of the graph. On the one hand, for acyclic directed graphs of bounded degree and sub-exponential expansion, we show that the value of the game converges almost surely to a constant at an exponential rate dominated in terms of the expansion. On the other hand, for the infinite d-ary tree that does not fall into the previous class of graphs, we show convergence at a double-exponential rate in terms of the expansion.}, author = {Attia, Luc and Lichev, Lyuben and Mitsche, Dieter and Saona Urmeneta, Raimundo J and Ziliotto, Bruno}, booktitle = {arXiv}, title = {{Zero-sum random games on directed graphs}}, doi = {10.48550/arXiv.2401.16252}, year = {2024}, } @article{18266, abstract = {Matrix games are the most basic model in game theory, and yet robustness with respect to small perturbations of the matrix entries is not fully understood. In this paper, we introduce value positivity and uniform value positivity, two properties that refine the notion of optimality in the context of polynomially perturbed matrix games. The first concept captures how the value depends on the perturbation parameter, and the second consists of the existence of a fixed strategy that guarantees the value of the unperturbed matrix game for every sufficiently small positive parameter. We provide polynomial-time algorithms to check whether a polynomially perturbed matrix game satisfies these properties. We further provide the functional form for a parameterized optimal strategy and the value function. Finally, we translate our results to linear programming and stochastic games, where value positivity is related to the existence of robust solutions.}, author = {Chatterjee, Krishnendu and Oliu-Barton, Miquel and Saona Urmeneta, Raimundo J}, issn = {1526-5471}, journal = {Mathematics of Operations Research}, number = {4}, pages = {2433--3282}, publisher = {Institute for Operations Research and the Management Sciences}, title = {{Value-positivity for matrix games}}, doi = {10.1287/moor.2022.0332}, volume = {50}, year = {2024}, } @inproceedings{12676, abstract = {Turn-based stochastic games (aka simple stochastic games) are two-player zero-sum games played on directed graphs with probabilistic transitions. The goal of player-max is to maximize the probability to reach a target state against the adversarial player-min. These games lie in NP ∩ coNP and are among the rare combinatorial problems that belong to this complexity class for which the existence of polynomial-time algorithm is a major open question. While randomized sub-exponential time algorithm exists, all known deterministic algorithms require exponential time in the worst-case. An important open question has been whether faster algorithms can be obtained parametrized by the treewidth of the game graph. Even deterministic sub-exponential time algorithm for constant treewidth turn-based stochastic games has remain elusive. In this work our main result is a deterministic algorithm to solve turn-based stochastic games that, given a game with n states, treewidth at most t, and the bit-complexity of the probabilistic transition function log D, has running time O ((tn2 log D)t log n). In particular, our algorithm is quasi-polynomial time for games with constant or poly-logarithmic treewidth.}, author = {Chatterjee, Krishnendu and Meggendorfer, Tobias and Saona Urmeneta, Raimundo J and Svoboda, Jakub}, booktitle = {Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms}, isbn = {9781611977554}, location = {Florence, Italy}, pages = {4590--4605}, publisher = {Society for Industrial and Applied Mathematics}, title = {{Faster algorithm for turn-based stochastic games with bounded treewidth}}, doi = {10.1137/1.9781611977554.ch173}, year = {2023}, } @unpublished{17100, abstract = {Prophet inequalities are a central object of study in optimal stopping theory. A gambler is sent values online, sampled from an instance of independent distributions, in an adversarial, random or selected order, depending on the model. When observing each value, the gambler either accepts it as a reward or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is maximising the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations. The model, in which the gambler selects the arrival order first, and then observes the values, is known as Order Selection. In this model a ratio of 0.7251 has been proved to be attainable for any instance. In very recent work, this has been improved up to 0.7258. If the gambler chooses the arrival order (uniformly) at random, we obtain the Random Order model. The worst case ratio over all possible instances has been extensively studied for at least 40 years. In the recent work aforementioned, through simulations, this ratio has been shown to be at most 0.7254 for the Random Order model, thus establishing for the first time that carefully choosing the order, instead of simply taking it at random, benefits the gambler. We give an alternative, more rigorous proof of this fact, by showing mathematically that in the Random Order model, no algorithm can achieve a ratio larger than 0.7235. This sets a new state-of-the-art hardness for this model, and establishes more formally that there is a real benefit in choosing the order.}, author = {Giambartolomei, Giordano and Frederik Mallmann-Trenn, Frederik Mallmann-Trenn and Saona Urmeneta, Raimundo J}, booktitle = {arXiv}, title = {{Prophet inequalities: Separating random order from order selection}}, doi = {10.48550/arXiv.2304.04024}, year = {2023}, } @article{11447, abstract = {Empirical essays of fitness landscapes suggest that they may be rugged, that is having multiple fitness peaks. Such fitness landscapes, those that have multiple peaks, necessarily have special local structures, called reciprocal sign epistasis (Poelwijk et al. in J Theor Biol 272:141–144, 2011). Here, we investigate the quantitative relationship between the number of fitness peaks and the number of reciprocal sign epistatic interactions. Previously, it has been shown (Poelwijk et al. in J Theor Biol 272:141–144, 2011) that pairwise reciprocal sign epistasis is a necessary but not sufficient condition for the existence of multiple peaks. Applying discrete Morse theory, which to our knowledge has never been used in this context, we extend this result by giving the minimal number of reciprocal sign epistatic interactions required to create a given number of peaks.}, author = {Saona Urmeneta, Raimundo J and Kondrashov, Fyodor and Khudiakova, Kseniia}, issn = {1522-9602}, journal = {Bulletin of Mathematical Biology}, keywords = {Computational Theory and Mathematics, General Agricultural and Biological Sciences, Pharmacology, General Environmental Science, General Biochemistry, Genetics and Molecular Biology, General Mathematics, Immunology, General Neuroscience}, number = {8}, publisher = {Springer Nature}, title = {{Relation between the number of peaks and the number of reciprocal sign epistatic interactions}}, doi = {10.1007/s11538-022-01029-z}, volume = {84}, year = {2022}, } @unpublished{12677, abstract = {In modern sample-driven Prophet Inequality, an adversary chooses a sequence of n items with values v1,v2,…,vn to be presented to a decision maker (DM). The process follows in two phases. In the first phase (sampling phase), some items, possibly selected at random, are revealed to the DM, but she can never accept them. In the second phase, the DM is presented with the other items in a random order and online fashion. For each item, she must make an irrevocable decision to either accept the item and stop the process or reject the item forever and proceed to the next item. The goal of the DM is to maximize the expected value as compared to a Prophet (or offline algorithm) that has access to all information. In this setting, the sampling phase has no cost and is not part of the optimization process. However, in many scenarios, the samples are obtained as part of the decision-making process. We model this aspect as a two-phase Prophet Inequality where an adversary chooses a sequence of 2n items with values v1,v2,…,v2n and the items are randomly ordered. Finally, there are two phases of the Prophet Inequality problem with the first n-items and the rest of the items, respectively. We show that some basic algorithms achieve a ratio of at most 0.450. We present an algorithm that achieves a ratio of at least 0.495. Finally, we show that for every algorithm the ratio it can achieve is at most 0.502. Hence our algorithm is near-optimal.}, author = {Chatterjee, Krishnendu and Mohammadi, Mona and Saona Urmeneta, Raimundo J}, booktitle = {arXiv}, title = {{Repeated prophet inequality with near-optimal bounds}}, doi = {10.48550/ARXIV.2209.14368}, year = {2022}, } @article{9311, abstract = {Partially observable Markov decision processes (POMDPs) are standard models for dynamic systems with probabilistic and nondeterministic behaviour in uncertain environments. We prove that in POMDPs with long-run average objective, the decision maker has approximately optimal strategies with finite memory. This implies notably that approximating the long-run value is recursively enumerable, as well as a weak continuity property of the value with respect to the transition function. }, author = {Chatterjee, Krishnendu and Saona Urmeneta, Raimundo J and Ziliotto, Bruno}, issn = {1526-5471}, journal = {Mathematics of Operations Research}, keywords = {Management Science and Operations Research, General Mathematics, Computer Science Applications}, number = {1}, pages = {100--119}, publisher = {Institute for Operations Research and the Management Sciences}, title = {{Finite-memory strategies in POMDPs with long-run average objectives}}, doi = {10.1287/moor.2020.1116}, volume = {47}, year = {2022}, }