Author name cluster

Jakub Svoboda

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

2 author rows

AAAI Conference 2025 Conference Paper

Linear Equations with Min and Max Operators: Computational Complexity

Krishnendu Chatterjee
Ruichen Luo
Raimundo Saona
Jakub Svoboda

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.

PDF Details DOI

ICML Conference 2024 Conference Paper

Reinforcement Learning from Reachability Specifications: PAC Guarantees with Expected Conditional Distance

Jakub Svoboda
Suguman Bansal
Krishnendu Chatterjee

Reinforcement Learning (RL) from temporal logical specifications is a fundamental problem in sequential decision making. One of the basic and core such specification is the reachability specification that requires a target set to be eventually visited. Despite strong empirical results for RL from such specifications, the theoretical guarantees are bleak, including the impossibility of Probably Approximately Correct (PAC) guarantee for reachability specifications. Given the impossibility result, in this work we consider the problem of RL from reachability specifications along with the information of expected conditional distance (ECD). We present (a) lower bound results which establish the necessity of ECD information for PAC guarantees and (b) an algorithm that establishes PAC-guarantees given the ECD information. To the best of our knowledge, this is the first RL from reachability specifications that does not make any assumptions on the underlying environment to learn policies.

Details

TCS Journal 2024 Journal Article

Weighted packet selection for rechargeable links in cryptocurrency networks: Complexity and approximation

Stefan Schmid
Jakub Svoboda
Michelle Yeo

We consider a natural problem dealing with weighted packet selection across a rechargeable link, which e. g. , finds applications in cryptocurrency networks. The capacity of a link ( u, v ) is determined by how many nodes u and v allocate for this link. Specifically, the input is a finite ordered sequence of packets that arrive in both directions along a link. Given ( u, v ) and a packet of weight x going from u to v, node u can either accept or reject the packet. If u accepts the packet, the capacity on link ( u, v ) decreases by x. Correspondingly, v's capacity on ( u, v ) increases by x. If a node rejects the packet, this will entail a cost affinely linear in the weight of the packet. A link is “rechargeable” in the sense that the total capacity of the link has to remain constant, but the allocation of capacity at the ends of the link can depend arbitrarily on the nodes' decisions. The goal is to minimise the sum of the capacity injected into the link and the cost of rejecting packets. We show that the problem is NP-hard, but can be approximated efficiently with a ratio of ( 1 + ε ) ⋅ ( 1 + 3 ) for some arbitrary ε > 0.

Details DOI

SODA Conference 2023 Conference Paper

Faster Algorithm for Turn-based Stochastic Games with Bounded Treewidth

Krishnendu Chatterjee
Tobias Meggendorfer
Raimundo Saona
Jakub Svoboda

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 (( tn 2 log D ) t log n ). In particular, our algorithm is quasi-polynomial time for games with constant or poly-logarithmic treewidth.

Details

Highlights Conference 2023 Conference Abstract

Stochastic Games with Bounded Treewidth

Jakub Svoboda

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 but the existence of polynomial-time algorithm is a major open question, 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. In this work our main result is a deterministic algorithm to solve turn-based stochastic games that, given a gamewith n states, treewidth at most t, and the bit-complexity of the probabilistic transition function log D, has running time O((tn^2 log D)^(t log n)). In particular, our algorithm is quasi-polynomial time for games with constant or poly-logarithmic treewidth. The main result was published in SODA'23. Contributed talk given by Jakub Svoboda

Details

MFCS Conference 2020 Conference Paper

Simplified Game of Life: Algorithms and Complexity

Krishnendu Chatterjee
Rasmus Ibsen-Jensen
Ismaël Jecker
Jakub Svoboda

Game of Life is a simple and elegant model to study dynamical system over networks. The model consists of a graph where every vertex has one of two types, namely, dead or alive. A configuration is a mapping of the vertices to the types. An update rule describes how the type of a vertex is updated given the types of its neighbors. In every round, all vertices are updated synchronously, which leads to a configuration update. While in general, Game of Life allows a broad range of update rules, we focus on two simple families of update rules, namely, underpopulation and overpopulation, that model several interesting dynamics studied in the literature. In both settings, a dead vertex requires at least a desired number of live neighbors to become alive. For underpopulation (resp. , overpopulation), a live vertex requires at least (resp. at most) a desired number of live neighbors to remain alive. We study the basic computation problems, e. g. , configuration reachability, for these two families of rules. For underpopulation rules, we show that these problems can be solved in polynomial time, whereas for overpopulation rules they are PSPACE-complete.

Details